MINIMUM DEGREE SPANNING TREE

• INSTANCE: Graph $G=\left(V,E\right)$.

• SOLUTION: A spanning tree for G.

• MEASURE: The maximum degree of the spanning graph.

  
  

• Good News: Approximable with an absolute error guarantee of 1 [178].

• Bad News: Not approximable within 3/2$-\varepsilon$ for any $\varepsilon >0$ [182].

• Comment: APX-intermediate unless the polynomial-hierarchy collapses [125]. The generalization of the problem to Steiner trees is also approximable with an absolute error guarantee of 1 [178].

• Garey and Johnson: ND1