Premium
Hardness and approximation for network flow interdiction
Author(s) -
Chestnut Stephen R.,
Zenklusen Rico
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21739
Subject(s) - interdiction , approximation algorithm , flow network , maximum flow problem , flow (mathematics) , time complexity , mathematics , graph , complement (music) , combinatorics , mathematical optimization , computer science , algorithm , discrete mathematics , geometry , complementation , engineering , gene , phenotype , aerospace engineering , biochemistry , chemistry
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 ‐Subgraph. We show that any n ϵ ‐approximation algorithm for Network Flow Interdiction, or one of several variants, would imply a 2 n 4ϵ ‐approximation algorithm for Densest k ‐Subgraph, which is an improvement over past work in terms of the polynomial factor. We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s ‐ t ‐Cut problem, and transferring our results gives hardness and an approximation algorithm for that problem, as well. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(4), 378–387 2017