# On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction

On Short Paths Interdiction Problems: Total and Node-Wise Limited Interdiction - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Theory of Computing Systems

, Volume 43, Issue 2, pp 204–233

First Online: 10 July 2007

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 kv 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 ds,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 ds,t≥d. Finally, we also show that the same inapproximability bounds hold for undirected graphs and-or node elimination.

KeywordsApproximation algorithm Dijkstra’s algorithm Most vital arcs problem Cyclic game Maxmin mean cycle Minimal vertex cover Network inhibition Network interdiction This research was supported in part by NSF grant IIS-0118635 and by DIMACS, the NSF Center for Discrete Mathematics and 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.

Autor: Leonid Khachiyan - Endre Boros - Konrad Borys - Khaled Elbassioni - Vladimir Gurvich - Gabor Rudolf - Jihui Zhao