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

Open.

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

Categories

minimum spanning tree; optimization; point sets

Entry Revision History

S. P. Fekete, 30 July 2003.

Bibliography

Cha03

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

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.