MAXIMUM LEAF SPANNING TREE

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

• SOLUTION: A spanning tree for G.

• MEASURE: The number of leaves of the spanning tree.

  
  

• Good News: Approximable within 3 [362].

• Bad News: APX-complete [179].

• Comment: Other problems which aim at finding spanning trees that maximize a single objective function have been considered. In particular, the problems of finding a spanning tree that has maximum diameter, or maximum height with respect to a specified root are not in APX, the problems of finding a spanning tree that has maximum sum of the distances between all pairs of vertices, or maximum sum of the distances from a specified root, are not in PTAS [180]. The problem of finding a spanning tree that maximizes the number of paths that connect pairs of vertices and pass through a common arc is approximable within 1.072 [110].

• Garey and Johnson: ND2