@article{Khachiyan2008,
    Abstract = {Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A{\textrightarrow}ℝ+ 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{\backslash}sqrt{\{}5{\}}-21{\backslash}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.},
    Author = {Khachiyan, Leonid and Boros, Endre and Borys, Konrad and Elbassioni, Khaled and Gurvich, Vladimir and Rudolf, Gabor and Zhao, Jihui},
    File = {Khachiyan2008\_Article\_OnShortPathsInterdictionProble (0) (0) - a - a - j.pdf},
    ISSN = {1433-0490},
    Journal = {Theory of Computing Systems},
    Month = {Aug},
    Number = {2},
    Pages = {204--233},
    Title = {On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction},
    URL = {https://doi.org/10.1007/s00224-007-9025-6},
    Volume = {43},
    Year = {2008},
    bdsk-url-1 = {https://doi.org/10.1007/s00224-007-9025-6},
    date-added = {2019-04-12 08:00:59 +0200},
    date-modified = {2019-04-12 08:00:59 +0200},
    day = {01},
    doi = {10.1007/s00224-007-9025-6}
}

@article{Khachiyan2008, Abstract = {Given a directed graph G=(V,A) with a non-negative weight (length) function on its arcs w:A{\textrightarrow}ℝ+ 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{\backslash}sqrt{{}5{}}-21{\backslash}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.}, Author = {Khachiyan, Leonid and Boros, Endre and Borys, Konrad and Elbassioni, Khaled and Gurvich, Vladimir and Rudolf, Gabor and Zhao, Jihui}, File = {Khachiyan2008_Article_OnShortPathsInterdictionProble (0) (0) - a - a - j.pdf}, ISSN = {1433-0490}, Journal = {Theory of Computing Systems}, Month = {Aug}, Number = {2}, Pages = {204--233}, Title = {On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction}, URL = {https://doi.org/10.1007/s00224-007-9025-6}, Volume = {43}, Year = {2008}, bdsk-url-1 = {https://doi.org/10.1007/s00224-007-9025-6}, date-added = {2019-04-12 08:00:59 +0200}, date-modified = {2019-04-12 08:00:59 +0200}, day = {01}, doi = {10.1007/s00224-007-9025-6} }