next up previous
Next: Problem 55: Pallet Loading Up: The Open Problems Project Previous: Problem 53: Minimum-Turn Cycle


Problem 54: Traveling Salesman Problem in Solid Grid Graphs

Statement
What is the complexity of finding a shortest tour in a solid planar grid graph? A planar grid graph is a graph whose vertices are any set of points on the planar integer lattice and whose edges connect every pair of vertices at unit distance. Distances between nodes correspond to induced shortest-path distances in the graph, which corresponds to ``Manhattan'' distances. A grid graph is solid if it does not have any holes, i.e., its complement in the planar integer lattice is connected.
Origin
[IPS82] show that the problem is NP-complete in general planar grid graphs.
Status/Conjectures
Open.
Motivation
Partial and Related Results
[UL97] show that Hamiltonicity of a solid grid graph can be decided in polynomial time. Thus we can decide whether there is a tour of length equal to the number of vertices. In contrast, deciding Hamiltonicity is NP-hard in general planar grid graphs [IPS82].

[ABD+01] observe that finding the shortest tour is polynomially solvable when restricted to thin grid graphs, i.e., grid graphs that do not contain an induced 2×2 square. This problem asks about replacing the thin restriction with the solid restriction.

Related Open Problems
Minimum-Turn Cycle Cover in Planar Grid Graphs (Problem 53)
Appearances
Mentioned in [ABD+01].
Categories
traveling salesman; optimization; point sets; graphs
Entry Revision History
S. P. Fekete, 20 Dec. 2003; E. Demaine, 16 May 2004.

Bibliography

ABD+01
E. M. Arkin, M. A. Bender, E. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia.
Optimal covering tours with turn costs.
In Proc. 13th ACM-SIAM Sympos. Discrete Algorithms, pages 138-147, 2001.

IPS82
A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter.
Hamilton paths in grid graphs.
SIAM J. Comput., 11:676-686, 1982.

UL97
Christopher Umans and William Lenhart.
Hamiltonian cycles in solid grid graphs.
In Proc. 38th Annu. IEEE Sympos. Found. Comput. Sci., pages 496-507, 1997.


next up previous
Next: Problem 55: Pallet Loading Up: The Open Problems Project Previous: Problem 53: Minimum-Turn Cycle
The Open Problems Project - December 04, 2015