graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a degree-constrained spanning tree is a

spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is no ...

where the maximum

vertex degree In graph theory, the degree (or valency) of a vertex of a graph is the number of edges that are incident to the vertex; in a multigraph, a loop contributes 2 to a vertex's degree, for the two ends of the edge. The degree of a vertex v is denot ...

is limited to a certain constant ''k''. The degree-constrained spanning tree problem is to determine whether a particular

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

has such a spanning tree for a particular ''k''.

Formal definition

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

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

''k'' < ''n''. Question: Does G have a spanning tree in which no

node In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex). Node may refer to: In mathematics * Vertex (graph theory), a vertex in a mathematical graph *Vertex (geometry), a point where two or more curves, lines ...

has degree greater than ''k''?

NP-completeness

This problem is

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

. This can be shown by a reduction from the

Hamiltonian path problem The Hamiltonian path problem is a topic discussed in the fields of complexity theory and graph theory. It decides if a directed or undirected graph, ''G'', contains a Hamiltonian path, a path that visits every vertex in the graph exactly once. T ...

. 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

k+1

References

* *{{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 Spanning tree NP-complete problems