On short paths interdiction problems: Total and node-wise limited interdiction

Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ ℝ₊ and two terminals s,t V, our goal is to destroy all short directed paths from s to t in G by eliminating some arcs of A. This is known as the short paths interdiction problem. We consider several versions of it, and in each case analyze two subcases: total limited interdiction, when a fixed number k of arcs can be removed, and node-wise limited interdiction, when for each node v V a fixed number k(v) of out-going arcs can be removed. Our results indicate that the latter subcase is always easier than the former one. In particular, we show that the short paths node-wise interdiction problem can be efficiently solved by an extension of Dijkstra's algorithm. In contrast, the short paths total interdiction problem is known to be NP-hard. We strengthen this hardness result by deriving the following inapproximability bounds: Given k, it is NP-hard to approximate within a factor c<2 the maximum s-t distance d(s,t) obtainable by removing (at most) k arcs from G. Furthermore, given d, it is NP-hard to approximate within a factor c<10\sqrt{5}-21\approx1.36 the minimum number of arcs which has to be removed to guarantee d(s,t) d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and/or node elimination.