Hamiltonicity in max-degree-3 grid graphs is ASP-complete, enabling a T-metacell framework that proves ASP-completeness for 38 loop puzzles, 14 previously unknown to be NP-hard.
Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin Polygonal Grid Graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
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, superthin, degree-bounded, or solid grid graphs. They solved many combinations of these problems, proving them either polynomially solvable or NP-complete, but left three combinations open. In this paper, we prove two of these unsolved combinations to be NP-complete: Hamiltonicity of Square Polygonal Grid Graphs and Hamiltonicity of Hexagonal Thin Grid Graphs. We also consider a new restriction, where the grid graph is both thin and polygonal, and prove that Hamiltonicity then becomes polynomially solvable for square, triangular, and hexagonal grid graphs.
fields
cs.CC 1years
2024 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
Hamiltonicity in max-degree-3 grid graphs is ASP-complete, enabling a T-metacell framework that proves ASP-completeness for 38 loop puzzles, 14 previously unknown to be NP-hard.