- INSTANCE:
Graph
,
an integer ,
and a weight function
.
- SOLUTION:
A
*k*-spanning tree, i.e., a subtree*T*of*G*of at least*k*nodes. - MEASURE:
The weight of the tree, i.e.,
.

*Good News:*Approximable within 3 [184].*Bad News:*APX-complete [Kann, --].*Comment:*The restriction to points in the Euclidean plane admits a PTAS [33]. The analogous diameter and communication-cost*k*-spanning tree problems are not in APX [419].