Traveling salesman problem in solid grid graphs
A planar grid graph has as its vertices a set of points of the integer lattice $\mathbb{Z}^2$, two vertices being adjacent exactly when they are at distance $1$; the distance between two vertices is their shortest-path distance in the graph, a Manhattan-type distance. The graph is solid, or without holes, if the lattice points that are not vertices form a connected set. A tour visits every vertex and returns to its start.
Itai, Papadimitriou and Szwarcfiter proved that the shortest tour problem, and already Hamiltonicity, is NP-complete for general planar grid graphs. Umans and Lenhart gave a polynomial-time test for Hamiltonicity of solid grid graphs, so it can be checked efficiently whether the shortest tour is a Hamiltonian cycle. Arkin, Bender, Demaine, Fekete, Mitchell and Sethia noted that a shortest tour can be found in polynomial time in thin grid graphs, those with no induced $2 \times 2$ square.
Problem. What is the computational complexity of finding a shortest tour of a solid planar grid graph?
Source: Origin uncertain; Itai, Papadimitriou and Szwarcfiter (1982) treat general grid graphs; Problem 54 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- CO — Combinatorics
- Secondary
- MG, OC
- Keywords
- Hamiltonian cycle, solid grid graphs, The Open Problems Project, traveling salesman problem
References
@article{itai1982,
author = {Itai, A. and Papadimitriou, C. H. and Szwarcfiter, J. L.},
title = {Hamilton paths in grid graphs},
journal = {SIAM J. Comput.},
volume = {11},
year = {1982},
pages = {676--686},
}
@inproceedings{umans1997,
author = {Umans, Christopher and Lenhart, William},
title = {Hamiltonian cycles in solid grid graphs},
booktitle = {Proc. 38th Annual IEEE Symposium on Foundations of Computer Science},
year = {1997},
pages = {496--507},
}
@inproceedings{arkin2001,
author = {Arkin, E. M. and Bender, M. A. and Demaine, E. D. and Fekete, S. P. and Mitchell, J. S. B. and Sethia, S.},
title = {Optimal covering tours with turn costs},
booktitle = {Proc. 13th ACM-SIAM Symposium on Discrete Algorithms},
year = {2001},
pages = {138--147},
url = {https://erikdemaine.org/papers/SODA2001a/},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01094, "Traveling salesman problem in solid grid graphs", clopen.solutions.