Degree-bounded minimum spanning trees

Given nn points in the Euclidean plane, the degree-δδ minimum spanning tree (MST) problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most δδ. The problem is NP-hard for 2≤δ≤32≤δ≤3, while the NP-hardness of the problem is open for δ=4δ=4. The problem is polynomial-time solvable when δ=5δ=5. By presenting an improved approximation analysis for Chan’s degree-4 MST algorithm [T. Chan, Euclidean bounded-degree spanning tree ratios, Discrete & Computational Geometry 32 (2004) 177–194], we show that, for any arbitrary collection of points in the Euclidean plane, there always exists a degree-4 spanning tree of weight at most (2+2)/3<1.1381 times the weight of an MST.