Minimum Manhattan network is NP-complete

Abstract

A rectilinear path between two points p, q ε R2 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 R2, 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 segmentsc 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. © 2009 ACM.