In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, 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 not ...
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 denote ...
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 discre ...
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 (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
''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, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. This can be shown by a reduction from the
Hamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path (a path in an undirected or directed graph that visits each vertex exactly once) or a ...
. 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
.
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