Abstract
Given a set T of n points in ℝ2, a Manhattan network on T is a graph G with the property that for each pair of points in T, G contains a rectilinear path between them of length equal to their distance in the L 1-metric. The minimum Manhattan network problem is to find a Manhattan network of minimum length, i.e., minimizing the total length of the line segments in the network.
In this paper, we prove that the decision version of the MMN problem is strongly NP-complete, using a 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 a 3-CNF formula.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Benkert, M., Wolff, A., Widmann, F.: The minimum Manhattan network problem: a fast factor-3 approximation. In: Proceedings of the 8th Japanese Conference on Discrete and Computational Geometry, pp. 16–28 (2005)
Benkert, M., Wolff, A., Widmann, F., Shirabe, T.: The minimum Manhattan network problem: approximations and exact solutions. Comput. Geom., Theory Appl. 35, 188–208 (2006)
Chepoi, V., Nouioua, K., Vaxès, Y.: A rounding algorithm for approximating minimum Manhattan networks. Theor. Comput. Sci. 390, 56–69 (2008)
Gudmundsson, J., Klein, O., Knauer, C., Smid, M.: Small Manhattan networks and algorithmic applications for the Earth mover’s distance. In: Proceedings of the 23rd European Workshop on Computational Geometry, pp. 174–177 (2007)
Gudmundsson, J., Levcopoulos, C., Narasimhan, G.: Approximating a minimum Manhattan network. Nord. J. Comput. 8, 219–232 (2001)
Guo, Z., Sun, H., Zhu, H.: A fast 2-approximation algorithm for the minimum Manhattan network problem. In: Proceedings of the 4th International Conference on Algorithmic Aspects in Information Management, pp. 212–223 (2008)
Guo, Z., Sun, H., Zhu, H.: Greedy construction of 2-approximation minimum Manhattan network. In: Proceedings of the 19th International Symposium on Algorithms and Computation, pp. 4–15 (2008)
Kato, R., Imai, K., Asano, T.: An improved algorithm for the minimum Manhattan network problem. In: Proceedings of the 13th International Symposium on Algorithms and Computation, pp. 344–356 (2002)
Muñoz, X., Seibert, S., Unger, W.: The minimal Manhattan network problem in three dimensions. In: Proceedings of the 3rd International Workshop on Algorithms and Computation, pp. 369–380 (2009)
Nouioua, K.: Enveloppes de Pareto et Réseaux de Manhattan: caractérisations et algorithmes. PhD thesis, Université de la Méditerranée (2005)
Seibert, S., Unger, W.: A 1.5-approximation of the minimal Manhattan network problem. In: Proceedings of the 16th International Symposium on Algorithms and Computation, pp. 246–255 (2005)
Zachariasen, M.: A catalog of Hanan grid problems. Networks 38, 76–83 (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
The research was in parts supported by a GRF grant in Hong Kong, HKU 7116/08E.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Chin, F.Y.L., Guo, Z. & Sun, H. Minimum Manhattan Network is NP-Complete. Discrete Comput Geom 45, 701–722 (2011). https://doi.org/10.1007/s00454-011-9342-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-011-9342-z