Hamiltonian paths in solid grid graphs

A grid graph connects selected points of the square lattice that are one unit apart. A solid grid graph has no holes. Given two distinct vertices, can a path visit every vertex exactly once and start and end at those vertices?

Why it matters and what counts as progress

Why it matters: The unrestricted grid-graph problem is NP-complete. The solid restriction gives algorithms a geometric structure that can change the complexity.

What counts as progress: Give a polynomial-time decision or construction algorithm and prove its correctness for the stated solidity definition and endpoint assumptions. Name the computation model used for any running-time bound.

How the problem developed

  1. 1982 · Grid-graph complexity [1]

    Alon Itai, Christos H. Papadimitriou and Jayme Luiz Szwarcfiter Proved NP-completeness for general grid graphs and gave a criterion for rectangular grids.

  2. 1997 · Solid-grid cycles [2]

    Christopher Umans and William Lenhart Gave a polynomial-time algorithm for the cycle problem on solid grid graphs.

  3. 19 Oct 2026 · Polynomial-time endpoint algorithm [3]

    Z. Zzyzek with Claude Opus 5.5 A polynomial-time algorithm decides whether two designated vertices of a finite two-dimensional solid grid graph can be joined by a Hamiltonian path. The formal development gives correctness and an O((∣V∣+3)6)O((|V|+3)^{6}) bound in its stated step model.

AI contribution

Hamiltonian s–t paths in solid grid graphs are decided in polynomial time: an algorithm with a Lean 4 proof

Z. Zzyzek

A polynomial-time algorithm decides whether two designated vertices of a finite two-dimensional solid grid graph can be joined by a Hamiltonian path. The formal development gives correctness and an O((∣V∣+3)6)O((|V|+3)^{6}) bound in its stated step model.

AI involvementAI-autonomous
ImportanceNotable
Technical verificationFormal (Lean)
Human understandingFew
Paper date:

Sources

  1. Hamilton Paths in Grid Graphs
  2. Hamiltonian cycles in solid grid graphs
  3. Hamiltonian s–t paths in solid grid graphs are decided in polynomial time: an algorithm with a Lean 4 proof
  4. SolidGridGraphHamPath
Publication history