Degree-constrained spanning tree

In graph theory, a degree-constrained spanning tree is a spanning tree where the maximum vertex degree is limited to a certain constant k. The degree-constrained spanning tree problem is to determine whether a particular graph has such a spanning tree for a particular k.

Formal definition

Input: n-node undirected graph G(V,E); positive integer k ≤ n.

Question: Does G have a spanning tree in which no node has degree greater than k?

NP-completeness

This problem is NP-complete. This can be shown by a reduction from the Hamiltonian path problem. It remains NP-complete even if k is fixed to a value ≥ 2. If the problem is defined as the degree must be ≤ k, the k = 2 case of degree-confined spanning tree is the Hamiltonian path problem.

Approximation Algorithms

Furer and Raghavachari give an approximation algorithm for the problem which either shows that there is no tree of maximum degree k or returns a tree of maximum degree k+1. It is one of the

References

• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.1: ND1, pg.206.