Hardness and approximation for network flow interdiction

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 2n^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.