pith. sign in

arxiv: 2405.08377 · v2 · submitted 2024-05-14 · 💻 cs.CC

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles

MIT Hardness Group , Josh Brunner , Lily Chung , Erik D. Demaine , Jenny Diomidova , Della Hendrickson , Andy Tockman This is my paper

Pith reviewed 2026-05-24 01:35 UTC · model grok-4.3

classification 💻 cs.CC
keywords ASP-completenessHamiltonicitygrid graphsloop puzzlesparsimonious reductionNP search problems#P-completenessT-metacell
0
0 comments X

The pith

Hamiltonicity in maximum-degree-3 grid graphs is ASP-complete via a parsimonious reduction from every NP search problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that Hamilton cycles in grid graphs of maximum degree 3, whether directed or undirected, stand in polynomial-time bijection with the solutions of any NP search problem. This ASP-completeness immediately yields that counting the cycles is #P-complete and that finding an extra cycle given k existing ones is NP-complete. The authors introduce a T-metacell framework that reduces the task of proving ASP-completeness for rectangular puzzles to the construction of a single gadget representing one degree-3 vertex. They then apply the framework to establish ASP-completeness for 38 loop-drawing puzzles and for certain restricted forms of Tree-Residue Vertex-Breaking.

Core claim

Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) admits a parsimonious reduction from every NP search problem, supplying a polynomial-time bijection between solution sets. When the vertices form a complete rectangular array, the same property holds if edges are directed or if some edges may be omitted, but the complete undirected rectangular grid is already known to be easy.

What carries the argument

The T-metacell framework, which reduces ASP-completeness proofs for rectangular loop puzzles to the design of one gadget per degree-3 grid-graph vertex.

If this is right

  • Given k Hamiltonian cycles, finding one more is NP-complete.
  • Counting Hamiltonian cycles is #P-complete.
  • Hamiltonicity remains ASP-complete for rectangular grids that are directed or that allow edge deletion.
  • Thirty-eight named loop puzzles are ASP-complete, fourteen of which had no prior NP-hardness proof.
  • Simple forms of Tree-Residue Vertex-Breaking, such as planar multigraphs with degree-6 breakable vertices, are ASP-complete.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The single-gadget reduction technique may apply directly to other cycle or path constraints on grids beyond the listed puzzles.
  • Similar parsimonious reductions could separate the complexity of counting versus existence for additional families of planar constraint problems.
  • The bijection property supplies a uniform way to transfer approximation or parameterized results from arbitrary NP search problems into grid Hamiltonicity.

Load-bearing premise

The gadget constructions produce a reduction that exactly matches the number of solutions without adding or omitting any.

What would settle it

An explicit NP search problem together with a grid-graph instance whose number of Hamiltonian cycles differs from the number of solutions of the original problem.

Figures

Figures reproduced from arXiv: 2405.08377 by Andy Tockman, Della Hendrickson, Erik D. Demaine, Jenny Diomidova, Josh Brunner, Lily Chung, MIT Hardness Group.

Figure 1
Figure 1. Figure 1: Illustration of Lemma 2.4. (iv) Directed Hamiltonian cycles of 𝐺1. (v) Kiki Euler tours of 𝐺2. (vi) Tree-Residue Vertex-Breakings of 𝐺3, where yellow vertices are breakable and blue vertices are unbreak￾able. Proof. Refer to [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The bijections we define for Lemma 2.4. (i) → (ii): Consider an assignment of colors to faces of 𝐺. For each vertex, two of the faces around it are one color and the third is the other color, so exactly two edges incident to it separate blue from white. The set of all edges separating blue from white thus forms a collection of cycles visiting each vertex once. We claim that this is actually a single cycle.… view at source ↗
Figure 3
Figure 3. Figure 3: Simulating a degree-4 unbreakable vertex using degree-4 breakable vertices (white) and degree-1 unbreakable vertices (black) [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Simulating a degree-4 unbreakable vertex using degree-6 breakable vertices. Figures 11 through 13 of [DR18]) but it is again parsimonious; indeed, [DR18, Lemmas 4.14 and 4.15] show that there is a bijection between Hamiltonian cycles in the input problem and solutions to the TRVB instance. Theorem 3.2. Planar ({𝑘}, {4})-TRVB is ASP-complete, for each 𝑘 ≥ 4. To further simplify our reductions, we will use a… view at source ↗
Figure 5
Figure 5. Figure 5: An example showing how reductions from TRVB to Hamiltonian cycle work. Definition 4.2. A rectangular grid graph is one whose vertex set consists of all lattice points within a rectangle. Definition 4.3. A graph is max-degree-3 if each of its vertices have degree at most 3. Definition 4.4. A spanning subgraph of 𝐺 is a subgraph of 𝐺 which contains all of the vertices (and some subset of the edges) of 𝐺. Not… view at source ↗
Figure 6
Figure 6. Figure 6: TRVB gadgets for directed grid graphs, showing two breakable degree-4 vertices connected by an edge and an unbreakable degree-1 vertex. We just need to ensure that gray edges cannot be used, which we can do by orienting them carefully. Ignoring the H-shaped construction in the center for the moment, each black edge is either the only edge pointing towards or the only edge pointing away from some vertex (de… view at source ↗
Figure 7
Figure 7. Figure 7: Filling holes in a directed rectangular grid graph [PITH_FULL_IMAGE:figures/full_fig_p012_7.png] view at source ↗
Figure 8
Figure 8. Figure 8 [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9 [PITH_FULL_IMAGE:figures/full_fig_p013_9.png] view at source ↗
Figure 10
Figure 10. Figure 10 [PITH_FULL_IMAGE:figures/full_fig_p013_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: A breakable degree-6 TRVB vertex gadget for undirected max-degree-3 spanning subgraphs of rectangular grid graphs. In the undirected case, we can strengthen the assumption about forced edges. For undirected graphs, an edge is forced if it is incident to a degree-2 vertex, since both edges incident to such a vertex must be used in any Hamiltonian cycle. A degree-3 vertex in a subgraph of a grid graph has t… view at source ↗
Figure 12
Figure 12. Figure 12: A dumbbell (black) with two red tentacles attached to its in-loop and two blue tentacles attached to its out-loop. Vertices are colored black and white in a checkerboard. (Theorem 3.1) [DR18]. See [PITH_FULL_IMAGE:figures/full_fig_p015_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: A breakable degree-4 TRVB vertex gadget for undirected max-degree-3 grid graphs. Removing the vertices highlighted in white gives an unbreakable degree-4 vertex gadget [PITH_FULL_IMAGE:figures/full_fig_p016_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: A breakable degree-4 TRVB vertex gadget for directed max-degree-3 grid graphs. Proof. The proof is extremely similar to the previous proof. We again reduce from ({4}, {1})-TRVB. Our degree-4 breakable vertex gadget is shown in [PITH_FULL_IMAGE:figures/full_fig_p016_14.png] view at source ↗
read the original abstract

We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including a polynomial-time bijection between solutions). As a consequence, given k Hamiltonian cycles, it is NP-complete to find another; and counting Hamiltonian cycles is #P-complete. If we require the grid graph's vertices to form a full $m \times n$ rectangle, then we show that Hamiltonicity remains ASP-complete if the edges are directed or if we allow removing some edges (whereas including all undirected edges is known to be easy). These results enable us to develop a stronger "T-metacell" framework for proving ASP-completeness of rectangular puzzles, which requires building just a single gadget representing a degree-3 grid-graph vertex. We apply this general theory to prove ASP-completeness of 38 pencil-and-paper puzzles where the goal is to draw a loop subject to given constraints: Slalom, Onsen-meguri, Mejilink, Detour, Tapa-Like Loop, Kouchoku, Icelom; Masyu, Yajilin, Nagareru, Castle Wall, Moon or Sun, Country Road, Geradeweg, Maxi Loop, Mid-loop, Balance Loop, Simple Loop, Haisu, Reflect Link, Linesweeper; Vertex/Touch Slitherlink, Dotchi-Loop, Ovotovata, Building Walk, Rail Pool, Disorderly Loop, Ant Mill, Koburin, Mukkonn Enn, Rassi Silai, (Crossing) Ichimaga, Tapa, Canal View, Aqre, and Paintarea. The last 14 of these puzzles were not even known to be NP-hard. Along the way, we prove ASP-completeness of some simple forms of Tree-Residue Vertex-Breaking (TRVB), including planar multigraphs with degree-6 breakable vertices, or with degree-4 breakable and degree-1 unbreakable vertices.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that Hamiltonicity on maximum-degree-3 grid graphs (directed or undirected) is ASP-complete via parsimonious reductions from arbitrary NP search problems. It further shows ASP-completeness for rectangular grids when edges may be directed or selectively removed. A T-metacell framework is introduced that reduces the task of proving ASP-completeness for rectangular loop puzzles to the construction of a single gadget for a degree-3 vertex. This framework is applied to establish ASP-completeness (including for 14 puzzles not previously known to be NP-hard) for 38 specific loop puzzles. Along the way, ASP-completeness is shown for several restricted forms of planar Tree-Residue Vertex-Breaking.

Significance. If the claimed parsimonious bijections hold, the results supply a reusable, gadget-based toolkit that lifts many existing NP-hardness proofs for grid and loop problems to the stronger ASP setting (preserving solution counts exactly). The explicit reduction from planar TRVB and the case-by-case verification of entry/exit configurations for the T-metacell provide concrete, checkable evidence rather than black-box arguments. The breadth of the 38 applications demonstrates immediate utility for puzzle complexity.

minor comments (3)
  1. §3.2, Figure 7: the caption for the directed T-metacell gadget does not explicitly list the four admissible entry/exit pairs that survive the global cycle condition; adding this enumeration would make the parsimony argument easier to verify at a glance.
  2. §4.1, Table 1: the row for 'Rectangular directed grid' lists the result but does not cite the specific lemma or theorem number that contains the reduction; cross-referencing would improve navigability.
  3. §5, the list of 38 puzzles: several puzzle names (e.g., 'Ovotovata', 'Rassi Silai') lack a one-sentence rule summary or reference to their standard source; this would help readers unfamiliar with the puzzle set.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive review and recommendation to accept the manuscript. The referee's summary accurately captures our contributions on ASP-completeness for Hamiltonicity in max-degree-3 grid graphs and the T-metacell framework for loop puzzles.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation proceeds via explicit parsimonious reductions from known ASP-complete problems (planar TRVB) to Hamiltonicity on max-degree-3 grid graphs, supported by gadget diagrams, entry/exit case analysis, and the T-metacell construction. These steps are independent of the target result and do not reduce by construction to fitted parameters, self-definitions, or unverified self-citations. The framework and puzzle applications follow directly from the established reduction chain without circular renaming or ansatz smuggling. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard definitions of ASP-completeness and parsimonious reductions; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of NP search problems, ASP-completeness, and parsimonious reductions from complexity theory.
    Invoked to establish that the grid Hamiltonicity problem is as hard as any NP search problem.

pith-pipeline@v0.9.0 · 5934 in / 1290 out tokens · 35933 ms · 2026-05-24T01:35:37.868595+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

8 extracted references · 8 canonical work pages · 2 internal anchors

  1. [1]

    Demaine, Joshua Lockhart, and Jayson Lynch

    [DLL18] Erik D. Demaine, Joshua Lockhart, and Jayson Lynch. The computational complexity of Portal and other 3D video games. InProceedings of the 9th International Conference on Fun with Algorithms (FUN 2018), pages 19:1–19:22, La Maddalena, Italy, June

    work page 2018

  2. [2]

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

    [DR17] Erik D. Demaine and Mikhail Rudoy. Hamiltonicity is hard in thin or polygonal grid graphs, but easy in thin polygonal grid graphs. arXiv:1706.10046,

    work page internal anchor Pith review Pith/arXiv arXiv

  3. [3]

    Demaine and Mikhail Rudoy

    [DR18] Erik D. Demaine and Mikhail Rudoy. Tree-Residue Vertex-Breaking: a new tool for proving hardness. InProceedings of the 20th Scandinavian Symposium and Workshops on Algorithm Theory (SW AT 2018), pages 32:1–32:14, Malm¨o, Sweden, June

    work page 2018

  4. [4]

    Tree-Residue Vertex-Breaking: a new tool for proving hardness

    Full paper at arXiv:1706.07900. [For10] Michal Foriˇsek. Computational complexity of two-dimensional platform games. InProceedings of the 5th International Conference on Fun with Algorithms, pages 214–227, Ischia, Italy, June

    work page internal anchor Pith review Pith/arXiv arXiv

  5. [5]

    The computational complexity of finding Hamiltonian cycles in grid graphs of semiregular tessellations

    [HL18] Kaiying Hou and Jayson Lynch. The computational complexity of finding Hamiltonian cycles in grid graphs of semiregular tessellations. In Stephane Durocher and Shahin Kamali, editors, Proceedings of the 30th Canadian Conference on Computational Geometry (CCCG 2018), pages 114–128, Winnipeg, Canada, August

    work page 2018

  6. [7]

    33 [Tan22] Hadyn Tang

    https://arXiv.org/abs/2004.12849. 33 [Tan22] Hadyn Tang. A framework for loop and path puzzle satisfiability NP-hardness results. arXiv:2202.02046,

    work page arXiv 2004

  7. [8]

    [Tut46] W

    https://arXiv.org/abs/2202.02046. [Tut46] W. T. Tutte. On Hamiltonian circuits.Journal of the London Mathematical Society, Series 1, 21(2):98–101,

    work page arXiv

  8. [9]

    Also IPSJ SIG Notes 2002-AL-87-2,

    work page 2002