Minimum Manhattan network is NP-complete

ABSTRACT

A rectilinear path between two points p,q∈ R² is a path connecting p and q with all its line segments horizontal or vertical segments. Furthermore, a Manhattan path between p and q is a rectilinear path with its length exactly dist(p,q):=|p.x-q.x|+|p.y-q.y|.

Given a set T of n points in R², a network G is said to be a Manhattan network on T, if for all p,q ∈ T there exists a Manhattan path between p and q with all its line segments in G. For the given point set T, the Minimum Manhattan Network (MMN) Problem is to find a Manhattan network G on T with the minimum network length.

In this paper, we shall prove that the decision version of MMN is strongly NP-complete, using the reduction from the well-known 3-SAT problem, which requires a number of gadgets. The gadgets have similar structures, but play different roles in simulating the 3-SAT formula. The reduction has been implemented with a computer program.

REFERENCES

• 1: M. Benkert, A. Wolff, and F. Widmann. The minimum Manhattan network problem: a fast factor-3 approximation. In Proceedings of the 8th Japanese Conference on Discrete and Computational Geometry, pages 16--28, 2005.
• 2: Marc Benkert , Alexander Wolff , Florian Widmann , Takeshi Shirabe, The minimum Manhattan network problem: approximations and exact solutions, Computational Geometry: Theory and Applications, v.35 n.3, p.188-208, October 2006 [doi>10.1016/j.comgeo.2005.09.004]
• 3: Victor Chepoi , Karim Nouioua , Yann Vaxès, A rounding algorithm for approximating minimum Manhattan networks, Theoretical Computer Science, v.390 n.1, p.56-69, January, 2008 [doi>10.1016/j.tcs.2007.10.013]
• 4: Joachim Gudmundsson , Christos Levcopoulos , Giri Narasimhan, Approximating a minimum Manhattan network, Nordic Journal of Computing, v.8 n.2, p.219-232, Summer 2001
• 5: Zeyu Guo , He Sun , Hong Zhu, A Fast 2-Approximation Algorithm for the Minimum Manhattan Network Problem, Proceedings of the 4th international conference on Algorithmic Aspects in Information and Management, p.212-223, June 23-25, 2008, Shanghai, China [doi>10.1007/978-3-540-68880-8_21]
• 6: Zeyu Guo , He Sun , Hong Zhu, Greedy Construction of 2-Approximation Minimum Manhattan Network, Proceedings of the 19th International Symposium on Algorithms and Computation, December 15-17, 2008, Gold Coast, Australia [doi>10.1007/978-3-540-92182-0_4]
• 7: Ryo Kato , Keiko Imai , Takao Asano, An Improved Algorithm for the Minimum Manhattan Network Problem, Proceedings of the 13th International Symposium on Algorithms and Computation, p.344-356, November 21-23, 2002
• 8: K. Nouioua. Enveloppes de Pareto et Reseaux de Manhattan: Caracterisations et algorithmes. Ph.D. thesis, Universite de la Mediterranee, 2005
• 9: S. Seibert and W. Unger. A 1.5-approximation of the minimal Manhattan network problem. In Proceedings of the 16th International Symposium on Algorithms and Computation, pages 246--255, 2005.
• 10: M. Zachariasen. A catalog of Hanan grid problems. Networks, 38:76--83, 2001.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Theory

Keywords:
3-sat, NP-complete, minimum Manhattan network