Degree-constrained spanning tree

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?

This problem is NP-complete (Garey & Johnson 1979). 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.

On a weighted graph, a Degree-constrained minimum spanning tree (DCMST) is a degree-constrained spanning tree in which the sum of its edges has the minimum possible sum. Finding a DCMST is an NP-Hard problem.^[1]

Heuristic algorithms that can solve the problem in polynomial time have been proposed, including Genetic and Ant-Based Algorithms.

Fürer & Raghavachari (1994) give an iterative polynomial time algorithm which, given a graph ${\displaystyle G}$, returns a spanning tree with maximum degree no larger than ${\displaystyle \Delta ^{*}+1}$, where ${\displaystyle \Delta ^{*}}$ is the minimum possible maximum degree over all spanning trees. Thus, if ${\displaystyle k=\Delta ^{*}}$, such an algorithm will either return a spanning tree of maximum degree ${\displaystyle k}$ or ${\displaystyle k+1}$.

For the complete bipartite graph ${\displaystyle K_{m,n}}$ where ${\displaystyle m\leq n}$:

${\displaystyle \Delta ^{*}(K_{m,n})=1+\left\lceil {\frac {n-1}{m}}\right\rceil }$