MAXIMUM MINIMUM METRIC K-SPANNING TREE

• INSTANCE: Graph $G=\left(V,E\right)$, length $l(e)\in N$ for each $e\in E$ satisfying the triangle inequality.

• SOLUTION: A subset $V' \subseteq V$ such that $\vert V'\vert=k$.

• MEASURE: Cost of the minimum spanning tree of the subgraph induced by V'.

  
  

• Good News: Approximable within 4 [225].

• Bad News: APX-complete and not approximable within 2$-\varepsilon$ for any $\varepsilon >0$ [225].

• Comment: Also called Maximum Remote Minimum Spanning Tree. Reduction from MAXIMUM INDEPENDENT SET. As hard to approximate as MAXIMUM INDEPENDENT SET for non-metric graphs. Approximable within 2.252 in the Euclidean metric, but not known to be NP-complete. MAXIMUM MINIMUM K-STEINER TREE is approximable within 3 and not approximable within 4/3$-\varepsilon$, but approximable within 2.16 in the Euclidean metric. MAXIMUM MINIMUM METRIC K-TSP is approximable within 3 and not approximable within 2$-\varepsilon$.