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.
Abstract The problems of computing the maximum increase in the weight of the minimum spanning trees of a graph caused by the removal of a given number of edges, or by finite increases in the weights of the edges, are investigated. For the case of edge removals, the problem is shown to be NP-hard and an Ω(1 log k )-approximation algorithm is presented for it, where (input parameter) k > 1 is the number of edges to be removed. The second problem is studied, assuming that the increase in the weight of an edge has an associated cost proportional to the magnitude of the change. An O ( n 3 m 2 log( n 2 m )) time algorithm is presented to solve it. In this paper we give a method for solving certain budgeted optimization problems in strongly polynomial time. The method can be applied to several known budgeted problems, and in addition we show two new applications. The first one extends Frederickson’s and Solis-Oba’s result [G. N. Frederickson and R. Solis-Oba, Combinatorica, 18 (1998), pp. 503-518] to (poly)matroid intersections from single matroids. The second one is the budgeted version of the minimum cost circulation problem.