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 -> R+ and two terminals s, t epsilon 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 epsilon V a fixed number k(upsilon) of out-going arcs can be removed. Our results indicate that the latter sub-case 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 root 5-21 approximate to 1.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.