A Decomposition-Based Pseudoapproximation Algorithm for Network Flow Inhibition
Carl Burch, Robert D. Carr, Sven Oliver Krumke, MADHAV V. MARATHE, Cynthia A. Phillips, Eric Sundberg · Kluwer Academic Publishers eBooks · 2005
In the network inhibition problem, we wish to expend a limited budget attacking a given edge-capacitated graph by “paying” to remove edge capacity from some subset of the edges. We wish to minimize the resulting maximum flow between two designated vertices s and t. The problem is strongly NP-hard. Previous approximation algorithms applied only to planar graphs. In this chapter, we give a polynomial-time algorithm, based on a linear-programming relaxation of an integer program, that finds an attack with cost B a and residual network capacity (max flow) C a such that $$ \frac{{B_a }} {B} + \in \frac{{C_a }} {{C^* }} \leqslant 1 + \in ,$$ where ε>0 is a given error parameter, B is the given budget (the amount of resources to expend damaging the network), and C* is the minimum (optimal) residual capacity for any attack with budget B. For example, our algorithm returns a (1,1+1/ε)-approximation or a (1+ε, 1)-pseudoapproximation, but we do not know which a priori. The parameter ε biases the nature of the solution, but does not affect the running time. We generalize the pseudoapproximation algorithm to multiple attack methods/budgets and give a polynomial-time algorithm to compute the most cost-effective attack.