AN APPROXIMATE MAX-FLOW MIN-CUT RELATION FOR UNDIRECTED MULTICOMMODITY FLOW, WITH APPLICATIONS

In this paper, we prove the first approximate max-flow min-cut theorem for undirected multicommodity flow. We show that for a feasible flow to exist in a multicommodity problem, it is sufficient that every cut's capacity exceeds its demand by a factor of O(log C log D), where C is the sum of all finite capacities and D is the sum of demands. Moreover, our theorem yields an algorithm for finding a cut that is approximately minimum relative to the flow that must cross it. We use this result to obtain an approximation algorithm for T. C. Hu's generalization of the multiway-cut problem. This algorithm can in turn be applied to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF= formula, via minimization, and other problems. We also generalize the theorem to hypergraph networks; using this generalization, we can handle CNF= clauses with an arbitrary number of literals per clause.