- INSTANCE:
Graph
.
- 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