3
$\begingroup$

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$:

graph

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:

  1. Remove $e$ from $T$, cutting $T$ into $T_1$ and $T_2$.
  2. Determine the next smallest edge $e'$ spanning $T_1$ and $T_2$ in $G$.
  3. 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.

$\endgroup$
  • $\begingroup$ Could we get the most helpful hint, that is, is this problem created by yourself or did you find the problem somewhere? $\endgroup$ – Apass.Jack Apr 4 at 1:03
  • $\begingroup$ @Apass.Jack Created by me and some other TAs. No online source that I know of (I've tried looking for it). $\endgroup$ – ryan Apr 4 at 1:04
  • $\begingroup$ @Apass.Jack I have good news! (Maybe?) I was informed that the problem was actually proposed in a competition a while ago (see here). However, the accepted solutions aren't necessarily optimal based on the scoring method listed. Also, there is no editorial :( $\endgroup$ – ryan Apr 4 at 4:59
  • $\begingroup$ @Apass.Jack after reading through a handful of solutions, it appears the best solution on there just brute-forces the whole problem quickly. That is, they compute the MST after removing each edge, then repeat this $k$ times. So this is not very helpful. Correction, there are a couple solutions that use the greedy strategy I recommended, which I guess is probably a good heuristic. $\endgroup$ – ryan Apr 4 at 5:05
  • 1
    $\begingroup$ In fact your second strategy is also greedy and does not work . The best removals for k=2 do not necessarly contain the best removal for k=1. $\endgroup$ – Vince Apr 4 at 12:55
3
$\begingroup$

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., & 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.

$\endgroup$
  • 1
    $\begingroup$ Thanks for this! Ironically enough, Frederickson is one of my professors. I should've asked him about this! $\endgroup$ – ryan Apr 4 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.