DIMACS TR: 2006-13
Inapproximability Bounds for Shortest-Path Network Interdiction Problems
Authors: Endre Boros, Konrad Borys, Vladimir Gurvich and Gabor Rudolf
ABSTRACT
We consider two network interdiction problems: one where a network
user tries to traverse a network from a starting vertex $s$ to a
target vertex $t$ along the shortest path while an interdictor tries
to eliminate all short $s$-$t$ paths by destroying as few vertices
(arcs) as possible, and one where the network user, as before, tries
to traverse the network from $s$ to $t$ along the shortest path
while the interdictor tries to destroy a fixed number of vertices
(arcs) so as to cause the biggest increase in the shortest $s$-$t$
path. The latter problem is known as the Most Vital Vertices (Arcs)
Problem. In this paper we provide inapproximability bounds for several
variants of these problems.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-13.pdf
DIMACS Home Page