next up previous
Next: Problem 49: Planar Euclidean Up: The Open Problems Project Previous: Problem 47: Hinged Dissections


Problem 48: Bounded-Degree Minimum Euclidean Spanning Tree

Statement
What is the complexity of finding a bounded-degree spanning tree for a planar point set, such that the total Euclidean length τk is as small as possible, subject to the constraint that no node has more than k = 4 edges incident to it?
Origin
Papadimitriou and Vazirani [PV84] conjectured the problem to be NP-hard for k = 4.
Status/Conjectures
Solved: Proved NP-hard in [FH09].
Motivation
Natural generalization of finding a shortest geometric Hamiltonian path; arises in network optimization
Partial and Related Results
[PV84] proved the problem to be NP-hard for k = 3. For k≥5, the problem is polynomially solvable, as there always is a minimum spanning tree with no point having degree more than 5.
Related Open Problems
Various worst-case ratios of minimum weight bounded-degree spanning trees for different degree bounds are still open, in particular comparing τk to the weight τ of a minimum spanning tree. [FKK+97] conjecture τ3/τ≤1.103..., τ4/τ≤1.035... for Euclidean distances in the plane, and τ4/τ≤1.25 for Manhattan distances in the plane, and give matching lower bounds.

[KRY96] show that for Euclidean distances, τ4/τ≤1.25 and τ3/τ≤1.5 in the plane, and τ3/τ≤1.66... in arbitrary dimensions.

The first two of these bounds were improved to τ4/τ≤1.143 and τ3/τ≤1.402 by [Cha03].

Now settled by NP-hard proof in [FH09].

Categories
minimum spanning tree; optimization; point sets
Entry Revision History
S. P. Fekete, 30 July 2003; J. O'Rourke, 29 Mar 2010 (thanks to Michael Hoffmann).

Bibliography

Cha03
Timothy M. Chan.
Euclidean bounded-degree spanning tree ratios.
In Proc. 19th ACM Sympos. Computational Geometry, pages 11-19, 2003.

FH09
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.

FKK+97
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.

KRY96
S. Khuller, B. Raghavachari, and N. Young.
Low-degree spanning trees of small weight.
SIAM J. Comput., 25:355-368, 1996.

PV84
C. H. Papadimitriou and U. V. Vazirani.
On two geometric problems related to the traveling salesman problem.
J. Algorithms, 5:231-246, 1984.


next up previous
Next: Problem 49: Planar Euclidean Up: The Open Problems Project Previous: Problem 47: Hinged Dissections
The Open Problems Project - December 04, 2015