23 citations · 62 across the 9 of their papers we have counts for
13 papers
Yin-Yang Puzzles are NP-complete
Erik D. Demaine, Jayson Lynch, Mikhail Rudoy +1
We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-paper puzzles. Viewed as a graph partitioning problem, we prove NP-completeness of partitioning a rectangular g…
Hardness of Token Swapping on Trees
Oswin Aichholzer, Erik D. Demaine, Matias Korman +6
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to us…
New Results in Sona Drawing: Hardness and TSP Separation
Man-Kwun Chiu, Erik D. Demaine, Jenny Diomidova +6
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its co…
Circumscribing Polygons and Polygonizations for Disjoint Line Segments
Hugo A. Akitaya, Matias Korman, Oliver Korten +3
Given a planar straight-line graph in , a \emph{circumscribing polygon} of is a simple polygon whose vertex set is , and every edge in is eit…
Cookie Clicker
Erik D. Demaine, Hiro Ito, Stefan Langerman +3
Cookie Clicker is a popular online incremental game where the goal of the game is to generate as many cookies as possible. In the game you start with an initial cookie generation r…
Computational Complexity of Motion Planning of a Robot through Simple Gadgets
Erik D. Demaine, Isaac Grosof, Jayson Lynch +1
We initiate a general theory for analyzing the complexity of motion planning of a single robot through a graph of "gadgets", each with their own state, set of locations, and allowe…
Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible
Zachary Abel, Jeffrey Bosboom, Michael Coulombe +7
We analyze the computational complexity of the many types of pencil-and-paper-style puzzles featured in the 2016 puzzle video game The Witness. In all puzzles, the goal is to draw…
Computational Complexity of Generalized Push Fight
Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy
We analyze the computational complexity of optimally playing the two-player board game Push Fight, generalized to an arbitrary board and number of pieces. We prove that the game is…
A simple proof that the -puzzle is hard
Erik D. Demaine, Mikhail Rudoy
The 15 puzzle is a classic reconfiguration puzzle with fifteen uniquely labeled unit squares within a board in which the goal is to slide the squares (without ever ove…
Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs
Erik D. Demaine, Mikhail Rudoy
In 2007, Arkin et al. initiated a systematic study of the complexity of the Hamiltonian cycle problem on square, triangular, or hexagonal grid graphs, restricted to polygonal, thin…
Tree-Residue Vertex-Breaking: a new tool for proving hardness
Erik D. Demaine, Mikhail Rudoy
In this paper, we introduce a new problem called Tree-Residue Vertex-Breaking (TRVB): given a multigraph some of whose vertices are marked "breakable," is it possible to conver…
Solving the Rubik's Cube Optimally is NP-complete
Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy
In this paper, we prove that optimally solving an Rubik's Cube is NP-complete by reducing from the Hamiltonian Cycle problem in square grid graphs. This impro…
Dissection with the Fewest Pieces is Hard, Even to Approximate
Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine +4
We prove that it is NP-hard to dissect one simple orthogonal polygon into another using a given number of pieces, as is approximating the fewest pieces to within a factor of $1+1/1…