On the Maximum Flow Network Interdiction Problem

Douglas Altner (altnerusna.edu)
Ozlem Ergun (oergunisye.gatech.edu)
Nelson Uhan (nhuhanpurdue.edu)

Abstract: In the Maximum Flow Network Interdiction Problem (MFNIP), we are given a finite budget to remove arcs from a network, and we want to determine which arcs we should remove in order to minimize the maximum flow in the network induced on the remaining arcs. This is a widely studied problem that has extensive applications, including those in military planning, drug interdiction, infection control in a hospital, and chemical treatment of raw sewage. In this paper, we primarily focus on the Cardinality Maximum Flow Network Interdiction Problem (CMFNIP), a special case of MFNIP where at most a pre-specified number of arcs may be removed. For this special case, we present two classes of valid inequalities that are separable in polynomial time. We also show that the integrality gap of the natural linear programming relaxation of Wood's integer linear programming formulation is not bounded below by a constant factor, even when the linear programming relaxation is strengthened by these valid inequalities. Finally, we give an approximation-factor-preserving reduction from the R-Interdiction Covering Problem (RIC), which is much simpler in structure to MFNIP; as a result, any hardness of approximation result for RIC immediately extends to MFNIP.

Keywords: Maximum Flow, Network Interdiction, Integrality Gap, Hardness of Approximation

Category 1: Network Optimization

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, March, 2008.

Download: [PDF]

Entry Submitted: 01/11/2008
Entry Accepted: 01/11/2008
Entry Last Modified: 12/04/2008

Modify/Update this entry