# 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 (Garey Johnson). 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.

## Degree-constrained minimum spanning tree

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.

## Approximation Algorithm

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

## References

- ↑ Bui, T. N. and Zrncic, C. M. 2006. An ant-based algorithm for finding degree-constrained minimum spanning tree. In GECCO ’06: Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 11–18, New York, NY, USA. ACM.

- Garey, Michael R.; Johnson, David S. (1979),
*Computers and Intractability: A Guide to the Theory of NP-Completeness*, W.H. Freeman, ISBN 978-0-7167-1045-5. A2.1: ND1, p. 206. - Fürer, Martin; Raghavachari, Balaji (1994), "Approximating the minimum-degree Steiner tree to within one of optimal",
*Journal of Algorithms***17**(3): 409–423, doi:10.1006/jagm.1994.1042.

Original source: https://en.wikipedia.org/wiki/Degree-constrained spanning tree.
Read more |