Approximate Max-Flow Min- (Multi) Cut Theorems and their Applications

Consider 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: min multicut over O(log k) =max flow = min multicut, where k is the number of commodities. Our proof is constructive; it enable us to find a multicut with 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 analyse the case of flows with specified demands, of Leighton-Roa and Klein et. al., and thereby obtain an improved bound for the later problem.