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 \tau_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\geq 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 \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].

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.