next up previous
Next: Problem 54: Traveling Salesman Up: The Open Problems Project Previous: Problem 52: Queue-Number of


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 90o turns? (An 180o 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] consider the problem in grid graphs, but are only able to give approximations.
Status/Conjectures
Open.
Motivation
Minimizing turns is a natural geometric measure; understanding its algorithmic behavior is of general interest.
Partial and Related Results
[ABD+01] show that the problem is polynomially solvable when restricted to thin grid graphs, i.e., grid graphs that do not contain an induced 2×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 known to be NP-complete, even for this special case.

More recent details and related problems can be found in the version [ABD+03].

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].
Categories
traveling salesman; optimization; point sets; graphs
Entry Revision History
S. P. Fekete, 12 Dec. 2003.

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.

ABD+03
E. M. Arkin, M. A. Bender, E. Demaine, S. P. Fekete, J. S. B. Mitchell, and S. Sethia.
Optimal covering tours with turn costs.
Manuscript (submitted), 2003.

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.


next up previous
Next: Problem 54: Traveling Salesman Up: The Open Problems Project Previous: Problem 52: Queue-Number of
The Open Problems Project - December 04, 2015