This problem is [[NP-complete]] {{harv|Garey|Johnson|1979}}. 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.
==Approximation Algorithm==
{{harvtxt|Fürer and |Raghavachari|1994}} gave an approximation algorithm for the problem which, on any given instance, either shows that therethe instance ishas no tree of maximum degree k or it finds and returns a tree of maximum degree k+1.
==References==
* {{cite bookcitation|authorauthor1-link = [[Michael R. Garey]]|first1=Michael and [[R.|last1=Garey|author2-link=David S. Johnson]]|first2=David S.|last2=Johnson | year = 1979 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]] | publisher = W.H. Freeman | isbn = 0-7167-1045-5}}|postscript=. A2.1: ND1, pgp. 206.}}
*{{cite articlecitation| authorfirst1=[[Martin|last1=Fürer]] and [[|first2=Balaji|last2=Raghavachari]]|year=1994|title=Approximating the Minimumminimum-Degreedegree Steiner Treetree to within Oneone of Optimaloptimal|journal=Journal of Algorithms }} |volume=17(|issue=3):409-423|pages=409–423|doi=10.1006/jagm.1994.1042|postscript=.}}
