MINIMUM K-SPANNING TREE

• INSTANCE: Graph $G=\left(V,E\right)$, an integer $k \leq n$, and a weight function $w : E \rightarrow N$.

• 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., $\sum_{e \in T}w(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].