An approximation algorithm for network flow interdiction with unit costs and two capacities

In the network flow interdiction problem, an interdictor aims to remove arcs of total cost at most a given budget B from a graph with given arc costs and capacities such that the value of a maximum flow from a source s to a sink t is minimized. Although the problem has high applicability in real world problems and is known to be strongly NP-hard, only few polynomial-time approximation algorithms are known. In this paper, we present a (B + 1)-approximation algorithm for the special case where arcs have unit costs and may only have a small or a large capacity. Thereby, we develop the first approximation algorithm for a variant of NFI whose approximation ratio only depends on the budget available to the interdictor, but not on the size of the graph.