DIMACS TR: 2006-13

Inapproximability Bounds for Shortest-Path Network Interdiction Problems

Authors: Endre Boros, Konrad Borys, Vladimir Gurvich and Gabor Rudolf


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