The Open Problems Project

Next: Problem 54: Traveling Salesman Problem in Solid Grid Graphs

Previous: Problem 52: Queue-Number of Planar Graphs

Problem 53: Minimum-Turn Cycle Cover in Planar Grid Graphs

Statement

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.

Origin

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.

Status/Conjectures

Solved: proved NP-hard by Fekete and Krupke [FK19]

Motivation

Minimizing turns is a natural geometric measure; understanding its algorithmic behavior is of general interest.

Partial and Related Results

[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.

Related Open Problems

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)

Appearances

[ABD+01], [ABD+05].

Categories

traveling salesman; optimization; point sets; graphs

Entry Revision History

S. P. Fekete, 12 Dec. 2003; D. Krupke, 29 Nov. 2023

Bibliography

[ABD+01]

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.

[ABD+05]

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.

[ACK+97]

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.

[FK19]

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.