The problem is as follows:
Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove at most $k$ edges from $E$ such that the resulting graph $G' = (V, E' \subseteq E, w)$ has a maximal weight minimum spanning tree over all possible $G'$.
I initially thought a greedy algorithm would work with "just remove the $k$ smallest edges as long as the graph remains connected." However, this does not work, consider the following graph and $k = 1$:
The MST of $G$ has weight 9. If we remove the minimal edge $(B, C)$, the MST of the resulting graph has weight 12. However, if we remove the edge $(A, B)$, the MST of the resulting graph has weight 13. So this greedy strategy does not work.
Other strategies, we can first note that it only helps to remove edges that are in the MST of $G$ initially. So we can first determine $T = MST(G)$. The next (inefficient) thing we could do is consider each edge in $e \in T$ and do:
- Remove $e$ from $T$, cutting $T$ into $T_1$ and $T_2$.
- Determine the next smallest edge $e'$ spanning $T_1$ and $T_2$ in $G$.
- Keep track of $e$ such that it maximizes $w(e') - w(e)$.
Repeat this $k$ times. This doesn't seem very efficient though. This would be something like $O(k \cdot n \cdot (n + m))$ I think. We could optimize this a bit by keeping track of an ordered set of edges on the cuts.
I am wondering if there exists an algorithm that is $O(km \log n)$ or better. Any approaches / advice would be appreciated.