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.
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. 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
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 .
Known cases
For the complete bipartite graph where :
References