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
ABSTRACT
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