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 no(1) -approximation
algorithm for network flow interdiction would imply an no(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.
keywords: network flow interdiction, approximation algorithms, hardness of approximation, budgeted optimization