- Formal definition
- NP-completeness
- Degree-constrained minimum spanning tree
- Approximation Algorithm
- References
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 {{harv|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.
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
{{harvtxt|Fürer|Raghavachari|1994}} give an iterative polynomial time algorithm which, given a graph
, returns a spanning tree with maximum degree no larger than 
, where 
is the minimum possible maximum degree over all spanning trees. Thus, if 
, such an algorithm will either return a spanning tree of maximum degree 
or 
.References
- {{citation|author1-link = Michael R. Garey|first1=Michael R.|last1=Garey|author2-link=David S. Johnson|first2=David S.|last2=Johnson | year = 1979 | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | publisher = W.H. Freeman | isbn = 978-0-7167-1045-5|postscript=. A2.1: ND1, p. 206.|title-link=Computers and Intractability: A Guide to the Theory of NP-Completeness}}
- {{citation|first1=Martin|last1=Fürer|first2=Balaji|last2=Raghavachari|year=1994|title=Approximating the minimum-degree Steiner tree to within one of optimal|journal=Journal of Algorithms|volume=17|issue=3|pages=409–423|doi=10.1006/jagm.1994.1042|postscript=.|citeseerx=10.1.1.136.1089}}