Degree-constrained spanning tree

File:Degree-constrained spanning tree.png is 2 (thus, a max degree 2 tree).
On the right, the central vertex must have degree at least 5 in any tree spanning this graph, so a 2 degree constrained tree cannot be constructed here.]]

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.Bui, T. N. and Zrncic, C. M. 2006. [http://www.cs.york.ac.uk/rts/docs/GECCO_2006/docs/p11.pdf 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.

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 $G$ , returns a spanning tree with maximum degree no larger than $\Delta^* + 1$ , where $\Delta^*$ is the minimum possible maximum degree over all spanning trees. Thus, if $k = \Delta^*$ , such an algorithm will either return a spanning tree of maximum degree $k$ or $k+1$ .

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}}

Category:Spanning tree

Category:NP-complete problems