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] 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 \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 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.