MAXIMUM MINIMUM SPANNING TREE DELETING K EDGES

• INSTANCE: Graph $G=\left(V,E\right)$, a weight function $w : E \rightarrow N$.

• SOLUTION: Subset $E'\subseteq E$ of k edges and a minimum spanning tree T in the graph $\left(V,E-E'\right)$.

• MEASURE: Weight of T.

  
  

• Good News: Approximable within $\log k$ [174].

• Comment: The good news is valid even if a minimum $\lambda$-edge connected subgraph of G is sought, for every $\lambda\ge 1$ [174].