Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, New Jersey (1993)
Ball, M.O., Golden, B.L., Vohra, R.V.: Finding the most vital arcs in a network. Oper. Res. Lett. 8, 73–76 (1989)
Bar-Noy, A., Khuller, S., Schieber, B.: The complexity of finding most vital arcs and nodes. Technical Report CS-TR-3539, University of Maryland, Institute of Advanced Computer Studies, College Park, MD (1995)
Beffara, E., Vorobyov, S.: Adapting Gurvich-Karzanov-Khachiyan’s algorithm for parity games: implementation and experimentation. Technical Report 020, Department of Information Technology, Uppsala University (2001) (available at http://www.it.uu.se/research/reports/#2001)
Beffara, E., Vorobyov, S.: Is randomized Gurvich-Karzanov-Khachiyan’s algorithm for parity games polynomial? Technical Report 025, Department of Information Technology, Uppsala University (2001) (available at http://www.it.uu.se/research/reports/#2001)
Björklund, H., Sandberg, S., Vorobyov, S.: A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discret. Appl. Math. 155(2), 210–229 (2007)
Clementi, A.E.F., Crescenzi, P., Rossi, G.: On the complexity of approximating colored-graph problems. In: COCOON, pp. 281–290 (1999)
Corely, H.W., Shaw, D.Y.: Most vital links and nodes in weighted networks. Oper. Res. Lett. 1, 157–160 (1982)
Dinur, I., Safra, S.: On the hardness of approximating minimum vertex cover. Ann. Math. 162, 439–485 (2005)
Ehrenfeucht, A., Mycielski, J.: Positional games over a graph. Not. Am. Math. Soc. 20, A-334 (1973)
Ehrenfeucht, A., Mycielski, J.: Positional strategies for mean payoff games. Int. J. Game Theory 8, 109–113 (1979)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596–615 (1987)
Fulkerson, D.R., Harding, G.C.: Maximizing the minimum source-sink path subject to a budget constraint. Math. Program. 13, 116–118 (1977)
Gallai, T.: Maximum-minimum Sätze über Graphen. Acta Math. Acad. Sci. Hung. 9, 395–434 (1958)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979)
Ghare, P.M., Montgomery, D.C., Turner, T.M.: Optimal interdiction policy for a flow network. Nav. Res. Logist. Q. 18, 37–45 (1971)
Golden, B.L.: A problem in network interdiction. Nav. Res. Logist. Q. 25, 711–713 (1978)
Goldschlager, L.M.: The monotone and planar circuit value problem are log space complete for P. SIGACT News 9(2), 25–29 (1977)
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)
Gurvich, V., Karzanov, A., Khachiyan, L.: Cyclic games and an algorithm to find minimax cycle means in directed graphs. USSR Comput. Math. Math. Phys. 28, 85–91 (1988)
Håstad, J.: Some optimal inapproximability results. In: STOC ’97: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 1–10. ACM Press (1997)
Israely, E., Wood, K.: Shortest-path network interdiction. Networks 40(2), 97–111 (2002)
Jurdzinski, M., Paterson, M., Zwick, U.: A deterministic subexponential algorithm for solving parity games. In: SODA 2006, pp. 117–123
Karakostas, G.: A better approximation ratio for the vertex cover problem. In: ICALP, pp. 1043–1050 (2005)
Karp, R.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum, New York (1972)
Karp, R.: A characterization of the minimum cycle mean in a digraph. Discret. Math. 23, 309–311 (1978)
Karzanov, A.V., Lebedev, V.N.: Cyclical games with prohibition. Math. Program. 60, 277–293 (1993)
Malik, K., Mittal, A.K., Gupta, S.K.: The k most vital arcs in the shortest path problem. Oper. Res. Lett. 8, 223–227 (1989)
McMasters, A.W., Mustin, T.M.: Optimal interdiction of a supply networks. Nav. Res. Logist. Q. 17, 261–268 (1970)
Moulin, H.: Prolongement des jeux à deux joueurs de somme nulle. Bull. Soc. Math. France, Memoire 45 (1976)
Moulin, H.: Extension of two person zero sum games. J. Math. Anal. Appl. 55(2), 490–507 (1976)
Phillips, C.A.: The network inhibition problem. In: Proceedings of the 25th Annual ACM Symposium on the Theory of Computing, pp. 776–785 (1993)
Pisaruk, N.N.: Mean cost cyclical games. Math. Oper. Res. 24(4), 817–828 (1999)
Poljak, S.: A note on the stable sets and coloring of graphs. Comment. Math. Univ. Carol. 15, 307–309 (1974)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, New York (2003)
Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)
Wagner, D.K.: Disjoint (s,t)-cuts in a network. Networks 20, 361–371 (1990)
Washburn, A., Wood, K.: Two-person zero-sum games for network interdiction. Oper. Res. 43(2), 243–251 (1995)
Wood, R.K.: Deterministic network interdiction. Math. Comput. Model. 17, 1–18 (1993)
Zwick, U., Paterson, M.: The complexity of mean payoff games on graphs. Theor. Comput. Sci. 158(1–2), 343–359 (1996)
Author information
Authors and Affiliations
Corresponding author
Additional 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.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License ( https://creativecommons.org/licenses/by-nc/2.0 ), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Khachiyan, L., Boros, E., Borys, K. et al. On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction. Theory Comput Syst 43, 204–233 (2008). https://doi.org/10.1007/s00224-007-9025-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-007-9025-6