On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction
Tóm tắt
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.
Tài liệu tham khảo
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)