Next: Problem 49: Planar Euclidean Maximum TSP
Previous: Problem 47: Hinged Dissections
What is the complexity of finding a bounded-degree spanning tree for a planar point set, such that the total Euclidean length \tau_k is as small as possible, subject to the constraint that no node has more than k=4 edges incident to it?
Papadimitriou and Vazirani [PV84] conjectured the problem to be NP-hard for k=4.
Solved: Proved NP-hard in [FH09].
Natural generalization of finding a shortest geometric Hamiltonian path; arises in network optimization
[PV84] proved the problem to be NP-hard for k=3. For k\geq 5, the problem is polynomially solvable, as there always is a minimum spanning tree with no point having degree more than 5.
Various worst-case ratios of minimum weight bounded-degree spanning trees for different degree bounds are still open, in particular comparing \tau_k to the weight \tau of a minimum spanning tree. [FKK+97] conjecture \tau_3/\tau \leq 1.103..., \tau_4/\tau \leq 1.035... for Euclidean distances in the plane, and \tau_4/\tau \leq 1.25 for Manhattan distances in the plane, and give matching lower bounds.
[KRY96] show that for Euclidean distances, \tau_4/\tau \leq 1.25 and \tau_3/\tau \leq 1.5 in the plane, and \tau_3/\tau \leq 1.66... in arbitrary dimensions.
The first two of these bounds were improved to \tau_4/\tau \leq 1.143 and \tau_3/\tau \leq 1.402 by [Cha03].
Now settled by NP-hard proof in [FH09].
minimum spanning tree; optimization; point sets
S. P. Fekete, 30 July 2003; J. O’Rourke, 29 Mar 2010 (thanks to Michael Hoffmann).
Timothy M. Chan. Euclidean bounded-degree spanning tree ratios. In Proc. 19th ACM Sympos. Computational Geometry, pages 11–19, 2003.
Andrea Francke and Michael Hoffmann. The Euclidean degree-4 minimum spanning tree problem is np-hard. In SCG ’09: Proceedings of the 25th annual symposium on Computational geometry, pages 179–188, New York, NY, USA, 2009. ACM.
S. P. Fekete, S. Khuller, M. Klemmstein, B. Raghavachari, and N. Young. A network flow technique for finding low-weight bounded-degree trees. Journal of Algorithms, 24:310–324, 1997.
S. Khuller, B. Raghavachari, and N. Young. Low-degree spanning trees of small weight. SIAM J. Comput., 25:355–368, 1996.
C. H. Papadimitriou and U. V. Vazirani. On two geometric problems related to the traveling salesman problem. J. Algorithms, 5:231–246, 1984.