Next: Problem 54: Traveling Salesman Problem in Solid Grid Graphs
Previous: Problem 52: Queue-Number of Planar Graphs
What is the complexity of finding a cycle-cover of a planar grid graph that has the fewest possible 90^\circ turns? (An 180^\circ U-turn counts as two turns.) 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.
Aggarwal et al. [ACK+97] show that the more general problem of finding a cycle cover for a planar set of points that minimizes total turn angle is NP-hard. Arkin et al. [ABD+01], [ABD+05] consider the problem in grid graphs, but are only able to give approximations.
Solved: proved NP-hard by Fekete and Krupke [FK19]
Minimizing turns is a natural geometric measure; understanding its algorithmic behavior is of general interest.
[ABD+01], [ABD+05] show that the problem is polynomially solvable when restricted to thin grid graphs, i.e., grid graphs that do not contain an induced 2 \times 2 square. For this special case, the problem behaves somewhat similarly to a Chinese Postman Problem. The problem of finding a minimum-turn tour is shown to be NP-complete, even for this special case.
In 2019, Fekete and Krupke [FK19] established that finding a minimum-turn cycle cover in a planar grid graph is NP-hard, thereby providing an answer to this problem.
Minimum-turn cycle cover in a “solid” (genus-zero) grid graph: What is the complexity of finding a minimum-turn tour for a given planar grid graph without holes?
TSP in a solid grid graph: What is the complexity of finding a minimum-length tour for a given planar grid graph without holes? (Problem 54)
traveling salesman; optimization; point sets; graphs
S. P. Fekete, 12 Dec. 2003; D. Krupke, 29 Nov. 2023
E. M. Arkin, M. A. Bender, E. D. 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.
E. M. Arkin, M. A. Bender, E. D. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia. Optimal covering tours with turn costs. SIAM Journal on Computing, 35(3):531–566, 2005.
Alok Aggarwal, Don Coppersmith, Sanjeev Khanna, Rajeev Motwani, and Baruch Schieber. The angular-metric traveling salesman problem. In Proc. 8thh Annual ACM-SIAM Sympos. Discrete Algorithms, pages 221–229, January 1997.
Sándor P. Fekete and Dominik Krupke. Covering tours and cycle covers with turn costs: Hardness and approximation. In Proceedings of the 11th International Conference on Algorithms and Complexity, volume 11485 of Lecture Notes in Computer Science, pages 224–236, Rome, Italy, May 2019.