The Euclidean degree-4 minimum spanning tree problem is NP-hard

ABSTRACT

We show that it is an NP-hard problem to decide for a given set P of n points in the Euclidean plane and a given parameter k∈R, whether P admits a spanning tree of maximum vertex degree four whose sum of edge lengths does not exceed k.

REFERENCES

• 1: S. Arora, Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.2, October 14-16, 1996
• 2: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 3: S. Arora and K. Chang. Approximation schemes for degree-restricted MST and red-blue separation problems. Algorithmica, 40(3):189--210, 2004.
• 4: Timothy M. Chan, Euclidean Bounded-Degree Spanning Tree Ratios, Discrete & Computational Geometry, v.32 n.2, p.177-194, July 2004 [doi>10.1007/s00454-004-1117-3]
• 5: E. D. Demaine, J. S. B. Mitchell, and J. O'Rourke. The Open Problems Project. http://maven.smith.edu/~orourke/TOPP/.
• 6: S. P. Fekete. Problem 48: Bounded-degree minimum Euclidean spanning tree. http://maven.smith.edu/~orourke/TOPP/P48.html.
• 7: Sándor P. Fekete , Samir Khuller , Monika Klemmstein , Balaji Raghavachari , Neal Young, A network-flow technique for finding low-weight bounded-degree spanning trees, Journal of Algorithms, v.24 n.2, p.310-324, Aug. 1997 [doi>10.1006/jagm.1997.0862]
• 8: M. R. Garey and D. S. Johnson. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 32:826--834, 1977.
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: Raja Jothi , Balaji Raghavachari, Degree-bounded minimum spanning trees, Discrete Applied Mathematics, v.157 n.5, p.960-970, March, 2009 [doi>10.1016/j.dam.2008.03.037]
• 11: Samir Khuller , Balaji Raghavachari , Neal Young, Low-Degree Spanning Trees of Small Weight, SIAM Journal on Computing, v.25 n.2, p.355-368, February 1996 [doi>10.1137/S0097539794264585]
• 12: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 13: Clyde Monma , Subhash Suri, Transitions in geometric minimum spanning trees, Discrete & Computational Geometry, v.8 n.3, p.265-293, 1992 [doi>10.1007/BF02293049]
• 14: C. H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoret. Comput. Sci., 4:237--244, 1977.
• 15: C. H. Papadimitriou and U. V. Vazirani. On two geometric problems related to the travelling salesman problem. J. Algorithms, 5:231--246, 1984.
• 16: Achilleas Papakostas , Ioannis G. Tollis, Algorithms for area-efficient orthogonal drawings, Computational Geometry: Theory and Applications, v.9 n.1-2, p.83-110, Jan. 1998 [doi>10.1016/S0925-7721(97)00017-5]
• 17: G. Robins and J. S. Salowe. Low-degree minimum spanning trees. Discrete Comput. Geom., 14(2):151--165, 1995.
• 18: R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230--1234, 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional 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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Theory

Keywords:
bounded-degree graphs, degree-constricted graphs, degree-restricted graphs, geometric graphs, geometric optimization, np-complete, reduction, spanning trees