Hamiltonicity is Hard in Thin or Polygonal Grid Graphs, but Easy in Thin\n Polygonal Grid Graphs

2017/06/30 by Erik D. Demaine, Mikhail Rudoy, Demaine, Erik D. +1 · 1 citation
Computer Science · #Interconnection Networks and Systems #Advanced Graph Theory Research #Complexity and Algorithms in Graphs

paper · pdf · doi:10.48550/arxiv.1706.10046

Abstract

In 2007, Arkin et al. initiated a systematic study of the complexity of the\nHamiltonian cycle problem on square, triangular, or hexagonal grid graphs,\nrestricted to polygonal, thin, superthin, degree-bounded, or solid grid graphs.\nThey solved many combinations of these problems, proving them either\npolynomially solvable or NP-complete, but left three combinations open. In this\npaper, we prove two of these unsolved combinations to be NP-complete:\nHamiltonicity of Square Polygonal Grid Graphs and Hamiltonicity of Hexagonal\nThin Grid Graphs. We also consider a new restriction, where the grid graph is\nboth thin and polygonal, and prove that Hamiltonicity then becomes polynomially\nsolvable for square, triangular, and hexagonal grid graphs.\n

Cited by

• Yin-Yang Puzzles are NP-complete

Related

• The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations
• Hamiltonicity in Semi-Regular Tessellation Dual Graphs
• Non-Hamiltonian Holes in Grid Graphs
• ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
• On Polynomial Solvability of the Hamiltonian Cycle Problem for Graphs of Degree Less Than or Equal To 3