publication . Article . Preprint . 2015

Hardness and approximation for network flow interdiction

Stephen R. Chestnut; Rico Zenklusen;
Open Access
  • Published: 08 Nov 2015 Journal: Networks, volume 69, pages 378-387 (issn: 0028-3045, Copyright policy)
  • Publisher: Wiley
In the Network Flow Interdiction problem, an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem, despite decades of interest in it. It is, surprisingly, nontrivial to obtain in polynomial time an approximation guarantee that is independent of the number of edges in the graph and their capacities. We present the first such approximation algorithm, which has approximation ratio at most 2(n−1) for any graph with n vertices. We complement the algorithm with a hardness theorem. Past work has shown that Network Flow Interdiction cannot be much easier to approximate than Densest k-Subg...
Persistent Identifiers
arXiv: Computer Science::Discrete Mathematics
free text keywords: Computer Networks and Communications, Hardware and Architecture, Software, Information Systems, Computer Science - Data Structures and Algorithms, Mathematics - Optimization and Control, Multi-objective optimization, Flow network, Discrete mathematics, Hardness of approximation, Time complexity, Vertex (geometry), Approximation algorithm, Interdiction, Polynomial, Computer science
Funded by
SNSF| New Approaches to Constrained Submodular Maximization
  • Funder: Swiss National Science Foundation (SNSF)
  • Project Code: 200021_165866
  • Funding stream: Project funding | Project funding (Div. I-III)
26 references, page 1 of 2

[1] N. Assimakopoulos. A network interdiction model for hospital infection control. Computers in Biology and Medicine, 17(6):413-422, 1987.

[2] C. Bazgan, S. Toubaline, and D. Vanderpooten. Complexity of determining the most vital elements for the p-median and p-center location problems. Journal of Combinatorial Optimization, 25(2):191-207, 2013. [OpenAIRE]

[3] C. Bazgan, S. Toubaline, and D. Vanderpooten. Critical edges for the assignment problem: Complexity and exact resolution. Operations Research Letters, 41(6):685- 689, 2013. [OpenAIRE]

[4] C. Bazgan, S. Toubaline, and D. Vanderpooten. Critical edges/nodes for the minimum spanning tree problem: complexity and approximation. Journal of Combinatorial Optimization, 26(1):178-189, 2013. [OpenAIRE]

[5] A. Bhaskara, M. Charikar, E. Chlamtac, U. Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. In Proceedings of the forty-second ACM Symposium on Theory of Computing, pages 201- 210, 2010.

[6] A. Bhaskara, M. Charikar, A. Vijayaraghavan, V. Guruswami, and Y. Zhou. Polynomial integrality gaps for strong SDP relaxations of Densest k-Subgraph. In Proceedings of the twenty-third annual ACM-SIAM Symposium on Discrete Algorithms, pages 388- 405, 2012.

[7] C. Burch, R. Carr, S. Krumke, M. Marathe, C. Phillips, and E. Sundberg. A decomposition-based pseudoapproximation algorithm for network flow inhibition. In Network Interdiction and Stochastic Integer Programming, pages 51-68. Springer, 2003.

[8] Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, and Yuan Zhou. Approximation algorithms and hardness of the k-route cut problem. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 780-799, 2012.

[9] M. Dinitz and A. Gupta. Packing interdiction and partial covering problems. In Integer Programming and Combinatorial Optimization, pages 157-168. Springer, 2013.

[10] U. Feige. Relations between average case complexity and approximation complexity. In Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, pages 534-543, 2002. [OpenAIRE]

[11] U. Feige, D. Peleg, and G. Kortsarz. The dense k-subgraph problem. Algorithmica, 29(3):410-421, 2001.

[12] Greg N Frederickson and Roberto Solis-Oba. Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2):244-266, 1999.

[13] T.E. Harris and F.S. Ross. Fundamentals of a method for evaluating rail net capacities. Technical Report RM-1573, RAND Corp. 1955.

[14] G. Joret and A. Vetta. Reducing the rank of a matroid. arXiv:1211.4853, 2012.

[15] Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, Gabor Rudolf, and Jihui Zhao. On short paths interdiction problems: total and nodewise limited interdiction. Theory of Computing Systems, 43(2):204-233, 2008.

26 references, page 1 of 2
Any information missing or wrong?Report an Issue