Hardness and approximation for network flow interdiction

DOI10.1002/NET.21739zbMATH Open1386.90026arXiv1511.02486OpenAlexW2962853446MaRDI QIDQ4638580FDOQ4638580

Authors: Rico Zenklusen, Stephen R. Chestnut 

Publication date: 27 April 2018

Published in: Networks (Search for Journal in Brave)

Abstract: 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. We present the first approximation hardness, showing that Network Flow Interdiction and several of its variants cannot be much easier to approximate than Densest k-Subgraph. In particular, any $n^{o(1)}$-approximation algorithm for Network Flow Interdiction would imply an $n^{o(1)}$-approximation algorithm for Densest k-Subgraph. We complement this hardness results with the first approximation algorithm for Network Flow Interdiction, which has approximation ratio 2(n-1). We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s-t-Cut problem, and transferring our results gives the first approximation hardness and algorithm for that problem, as well.

Full work available at URL: https://arxiv.org/abs/1511.02486

Recommendations

• An approximation algorithm for network flow interdiction with unit costs and two capacities
• Network flow interdiction on planar graphs
• Approximation algorithm for maximum flow network interdiction problem
• scientific article; zbMATH DE number 4055051
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• Network interdiction and stochastic integer programming
• Approximation and Online Algorithms
• Flow Problems in Multi-Interface Networks
• On the computational behavior of a polynomial-time network flow algorithm
• Combined Competitive Flow Control and Routing in Networks with Hard Side Constraints

zbMATH Keywords

approximation algorithmsmultiobjective optimizationnetwork flowhardness of approximationinterdictiondensest \(k\)-subgraph

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Programming involving graphs or networks (90C35) Communication networks in operations research (90B18)

Cited In (33)

• A \((B + 1)\)-approximation for network flow interdiction with unit costs
• Protection of flows under targeted attacks
• Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
• A Progressive Approximation Approach for the Exact Solution of Sparse Large-Scale Binary Interdiction Games
• On the hardness of approximating the min-hack problem
• Sherali-Adams integrality gaps matching the log-density threshold
• Maximizing convergence time in network averaging dynamics subject to edge removal
• Packing interdiction and partial covering problems
• Rerouting Flows when Links Fail
• A Scalable Lower Bound for the Worst-Case Relay Attack Problem on the Transmission Grid
• Vertex downgrading to minimize connectivity
• Parametric multiroute flow and its application to multilink-attack network
• Symmetric interdiction for matching problems
• Approximability of the k‐server disconnection problem
• Title not available (Why is that?)
• Interdicting structured combinatorial optimization problems with {0,1}-objectives
• Approximation algorithm for maximum flow network interdiction problem
• Interdicting facilities in tree networks
• The complexity of computing a robust flow
• Network flow interdiction on planar graphs
• Improved hardness for cut, interdiction, and firefighter problems
• Matrix interdiction problem
• Theoretical and computational advances for network diversion
• Interdiction problems on planar graphs
• On short paths interdiction problems: Total and node-wise limited interdiction
• An approximation algorithm for network flow interdiction with unit costs and two capacities
• An exact method for nonlinear network flow interdiction problems
• Blocking optimal structures
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Filtering undesirable flows in networks
• Analysis of budget for interdiction on multicommodity network flows
• The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability
• On the minimum \(s-t\) cut problem with budget constraints

This page was built for publication: Hardness and approximation for network flow interdiction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4638580)