Degree-constrained spanning tree: Difference between revisions

Revision as of 14:37, 12 April 2007

Revision as of 00:25, 12 July 2007

Line 1:

{{Expand|date=January 2007}}

{{Cleanup|date=December 2006}}

{{Wikify|date=December 2006}}

In [[graph theory]], a '''degree-constrained spanning tree''' is a [[spanning tree (mathematics)|spanning tree]] where the maximum [[Degree (graph theory)|vertex degree]] is limited to a certain [[constant]] ''k''. The '''degree-constrained spanning tree problem''' is to determine whether a particular [[Graph (mathematics)|graph]] has such a spanning tree for a particular ''k''. Formally:

==Formal definition==

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

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

Question: Does G have a spanning tree in which no [[Node (computer science)|node]] has degree greater than ''k''?

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 (in fact, for ''k''=2, this is the Hamiltonian path problem).

==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. (inIf factyou have defined that the degree must be <= ''k'', forthe ''k'' = 2, thiscase of degree-confined spanning tree is the Hamiltonian path problem).

==References==

* {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | id = ISBN 0-7167-1045-5}} A2.1: ND1, pg.206.

If you have defined that the degree must be <= k, the k=2 case of degree-confined spanning tree is the Hamiltonian path problem.

[[Category:Spanning tree]]

[[Category:NP-complete problems]]

{{stub}}