TY - JOUR

T1 - On short paths interdiction problems

T2 - Total and node-wise limited interdiction

AU - Khachiyan, Leonid

AU - Boros, Endre

AU - Borys, Konrad

AU - Elbassioni, Khaled

AU - Gurvich, Vladimir

AU - Rudolf, Gabor

AU - Zhao, Jihui

N1 - Funding Information:
This research was supported in part by NSF grant IIS-0118635 and by DIMACS, the NSF Center for Discrete Mathematics & Theoretical Computer Science. Preprints DTR-2005-04 and DTR-2006-13 are available at http://dimacs.rutgers.edu/TechnicalReports/2005.html and http://dimacs.rutgers.edu/TechnicalReports/2006/html. Our co-author Leonid Khachiyan passed away with tragic suddenness on April 29th, 2005.

PY - 2008/8

Y1 - 2008/8

N2 - Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ ℝ+ and two terminals s,t 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 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\approx1.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.

AB - Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A→ ℝ+ and two terminals s,t 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 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\approx1.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.

KW - Approximation algorithm

KW - Cyclic game

KW - Dijkstra's algorithm

KW - Maxmin mean cycle

KW - Minimal vertex cover

KW - Most vital arcs problem

KW - Network inhibition

KW - Network interdiction

UR - http://www.scopus.com/inward/record.url?scp=41849108807&partnerID=8YFLogxK

U2 - 10.1007/s00224-007-9025-6

DO - 10.1007/s00224-007-9025-6

M3 - Article

AN - SCOPUS:41849108807

SN - 1432-4350

VL - 43

SP - 204

EP - 233

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 2

ER -