Maximal Minimum Spanning Tree by Removing $k$ Edges The problem is as follows:


  Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 &lt; k &lt; |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.
This is known as the $k$ most vital edges for the minimum spanning tree problem. It has been proved as NP-hard [1]. 

For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function [2], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie's sensitivity analysis [3].



[1] Frederickson, G. N., &amp; Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2), 244-266.

[2] Liang, W. (2001). Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Applied Mathematics, 113(2-3), 319-327.

[3] Pettie, S. (2005, December). Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In International Symposium on Algorithms and Computation (pp. 964-973). Springer, Berlin, Heidelberg.