Approximate max-flow min-(multi)cut theorems and their applications

Abstract

Consider the multicommodity flow problem in which the object is to maximize the sum of commodities routed. We prove the following approximate max-flow min-multicut theorem: \[ \frac{{\min {\text{multicut}}}}{{O(\log k)}} \leqslant \max {\text{flow}} \leqslant \min {\text{multicut}}, \] where k is the number of commodities. Our proof is constructive; it enables us to find a multicut within $O(\log k)$ of the max flow (and hence also the optimal multicut). In addition, the proof technique provides a unified framework in which one can also analyze the case of flows with specified demands of Leighton and Rao and Klein et al. and thereby obtain an improved bound for the latter problem.