The 4-degree spanning tree problem also admits a PTAS, but the NP-hardness
of the problem is open .
The 5-degree problem is polynomial-time solvable.
In d-dimensional Euclidean space for
the 3-degree spanning tree
problem is approximable within 5/3. .
The generalization to a graph with metric weight function and for each
vertex Ưa degree bound d(v) is called
MINIMUM BOUNDED DEGREE SPANNING TREE and is approximable within
is the initial degree of v .