DIMACS TR: 2007-02

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

Authors: Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf and Jihui Zhao


Given a directed graph $G=(V,A)$ with a non-negative weight (length) function on its arcs $w : A \rightarrow \RR_+$ and two terminals $s,t \in 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 \emph{short paths interdiction problem}. We consider several versions of it, and in each case analyze two subcases: {\em total limited interdiction}, when a fixed number $k$ of arcs can be removed, and {\em node-wise limited interdiction}, when for each node $v \in 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 \approx 1.36$ the minimum number of arcs which has to be removed to guarantee $d(s,t) \geq d$. Finally, we also show that the same inapproximability bounds hold for non-directed graphs and/or node elimination.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-02.pdf
DIMACS Home Page