**Next:** Problem 49: Planar Euclidean Maximum TSP

**Previous:** Problem 47: Hinged Dissections

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

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