Degree-constrained spanning tree

Formal definition

Input: n-node undirected graph G(V,E); positive integer k

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