Degree-constrained spanning tree

<h2 id="formal-definition">Formal definition</h2>
<p>Input: <i>n</i>-node undirected graph G(V,E); positive <a href="/facts/Integer/PUwwrawx">integer</a> <i>k</i> < <i>n</i>.
</p><p>Question: Does G have a spanning tree in which no <a href="/facts/Node_(computer_science)/eYlvVE0z">node</a> has degree greater than <i>k</i>?
</p>
<h2 id="np-completeness">NP-completeness</h2>
<p>This problem is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> (Garey & Johnson 1979). This can be shown by a <a href="/facts/Reduction_(complexity)/IVWF7a1c">reduction</a> from the <a href="/facts/Hamiltonian_path_problem/heMgdfpa">Hamiltonian path problem</a>. It remains NP-complete even if <i>k</i> is fixed to a value ≥ 2. If the problem is defined as the degree must be ≤ <i>k</i>, the <i>k</i> = 2 case of degree-confined spanning tree is the Hamiltonian path problem.
</p>
<h2 id="degree-constrained-minimum-spanning-tree">Degree-constrained minimum spanning tree</h2>
<p>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.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p><p>Heuristic algorithms that can solve the problem in polynomial time have been proposed, including Genetic and Ant-Based Algorithms.
</p>
<h2 id="approximation-algorithm">Approximation Algorithm</h2>
<p>Fürer & Raghavachari (1994) give an iterative polynomial time algorithm which, given a graph 
  
    
      
        G
      
    
    {\displaystyle G}
  
, returns a spanning tree with maximum degree no larger than 
  
    
      
        
          Δ
          
            ∗
          
        
        +
        1
      
    
    {\displaystyle \Delta ^{*}+1}
  
, where 
  
    
      
        
          Δ
          
            ∗
          
        
      
    
    {\displaystyle \Delta ^{*}}
  
 is the minimum possible maximum degree over all spanning trees. Thus, if 
  
    
      
        k
        =
        
          Δ
          
            ∗
          
        
      
    
    {\displaystyle k=\Delta ^{*}}
  
, such an algorithm will either return a spanning tree of maximum degree 
  
    
      
        k
      
    
    {\displaystyle k}
  
 or 
  
    
      
        k
        +
        1
      
    
    {\displaystyle k+1}
  
.
</p>

<ul><li><a href="/facts/Michael_R._Garey/xuSLYs90">Garey, Michael R.</a>; <a href="/facts/David_S._Johnson/kGSBxucb">Johnson, David S.</a> (1979), <a href="/facts/Computers_and_Intractability:_A_Guide_to_the_Theory_of_NP-Completeness/04FE56Ss"><i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i></a>, W.H. Freeman, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-7167-1045-5. A2.1: ND1, p. 206.{{citation}}:  CS1 maint: postscript (link)</li>
<li>Fürer, Martin; Raghavachari, Balaji (1994), "Approximating the minimum-degree Steiner tree to within one of optimal", <i>Journal of Algorithms</i>, 17 (3): 409–423, <a href="/facts/CiteSeerX_(identifier)/SceDmd3c">CiteSeerX</a> <a href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.136.1089">10.1.1.136.1089</a>, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1006%2Fjagm.1994.1042">10.1006/jagm.1994.1042</a>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>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. <a href="http://www.cs.york.ac.uk/rts/docs/GECCO_2006/docs/p11.pdf" target="_blank">http://www.cs.york.ac.uk/rts/docs/GECCO_2006/docs/p11.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Degree-constrained spanning tree open-in-new

Degree-constrained spanning tree