Finding the \(k\) most vital edges with respect to minimum spanning tree (Q1806175)

For a connected, undirected and weighted graph \(G= (V, E)\), the problem of finding the \(k\) most vital edges of \(G\) with respect to minimum spanning tree is to find \(k\) edges in \(G\) whose removal will cause greatest weight increase in the minimum spanning tree of the remaining graph. This problem is known to be NP-hard for arbitrary \(k\). In this paper, we first describe a simple exact algorithm for this problem, based on the approach of edge replacement in the minimum spanning tree of \(G\). Next, we present polynomial-time randomized algorithms that produce optimal and approximate solutions to this problem. For \(|V|= n\) and \(|E|= m\), our algorithm producing optimal solution has a time complexity of \(O(mn)\) with probability of success at least \(e^{-{\sqrt{2k}\over k-2}}\), which is 0.90 for \(k\geq 200\) and asymptotically 1 when \(k\) goes to infinity. The algorithm producing approximate solution runs in \(O(mn+ nk^2\log k)\) time with probability of success at least \(1-{1\over 4}\left({2\over n}\right)^{k/2- 2}\), which is 0.998 for \(k\geq 10\), and produces solution within factor 2 to the optimal one. Finally, we show that both of our randomized algorithms can be easily parallelized. On a CREW PRAM, the first algorithm runs in \(O(n)\) time using \(n^2\) processors, and the second algorithm runs in \(O(\log^2n)\) time using \(mn/\log n\) processors and hence is RNC.