Traveling Salesman Problem in Solid Grid Graphs

Definitions and mathematical statement

For a finite set $V\subset\mathbb Z^2$, let $G$ contain exactly the unit horizontal and vertical edges whose endpoints both lie in $V$. Assume $G$ is connected. It is solid when the complementary lattice vertex set $\mathbb Z^2\setminus V$ is connected by unit horizontal and vertical steps, so it has no missing-vertex holes.

A tour is a closed walk in $G$ visiting every vertex at least once. Its length is the number of traversed edges, counted with multiplicity. Determine the computational complexity of finding a shortest tour in a solid grid graph. The associated decision problem supplies an integer $B$ and asks whether a tour of length at most $B$ exists; the vertices of $G$ are given explicitly.

Equivalently, one may solve the travelling-salesman problem on $V$ with the shortest-path metric $d_G$. This is the intrinsic graph distance. It need not equal the unrestricted Manhattan distance $\|u-v\|_1$, because an allowed path must remain in $G$.

A Hamiltonian cycle is the special case of a tour of length $|V|$. Deciding that special case alone does not determine the minimum tour length when repeated edges or vertices are necessary. The source asks whether the full optimization problem has a polynomial algorithm or a corresponding hardness classification.

Short English statement

Determine how hard it is to find the shortest closed walk visiting every vertex of a hole-free grid graph, allowing repeated visits.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 5500054 (AMR-054-0054), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problems Project - Computational Geometry, Problem 54. Original source indexed by AMR-054-0054. https://topp.openproblem.net/p54.