23 citations · 62 across the 9 of their papers we have counts for
4 papers · 1 filter
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…