Network interdiction problems are a natural way to study the sensitivity of a network optimization problem with respect to the removal of a limited set of edges or vertices. One of the oldest and best-studied interdiction problems is minimum spanning tree (MST) interdiction. Here, an undirected multigraph with nonnegative edge weights and positive interdiction costs on its edges is given, together with a positive budget B. The goal is to find a subset of edges R, whose total interdiction cost does not exceed B, such that removing R leads to a graph where the weight of an MST is as large as possible. Frederickson and Solis-Oba (SODA 1996) presented an O(log m)-approximation for MST interdiction, where m is the number of edges. Since then, no further progress has been made regarding approximations, and the question whether MST interdiction admits an O(1)-approximation remained open. We answer this question in the affirmative, by presenting a 14-approximation that overcomes two main hurdles that hindered further progress so far. Moreover, based on a well-known 2-approximation for the metric traveling salesman problem (TSP), we show that our O(1)-approximation for MST interdiction implies an O(1)-approximation for a natural interdiction version of metric TSP.
We highlight that @cite_10 claims to present a @math -approximation for the @math most vital edges problem for MST. However, the results in @cite_10 are based on an erroneous lemma about spanning trees. shortVersion We provide details on this erroneous lemma in the long version of the paper. In Appendix we provide details on this erroneous lemma.
@cite_10
2076304834
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 N P-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 - √ k-2 k-2 , which is 0.90 fork > 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 4 (2 n ) k 2-2 , which is 0.998 for k > 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 2 n) time using mn log n processors and hence is RNC.