Approximate max-integral-flow/min-multicut theorems

摘要

We establish several approximate max-integral-flow / min-multicut theorems. While in general this ratio can be very large, we prove strong approximation ratios in the case where the min-multicut is a constant fraction ε of the total capacity of the graph. This setting is motivated by several combinatorial and algorithmic applications. Prior to this work, a general max-integral-flow / min-multicut bound was known only for the special case where the graph is a tree. We prove that, for arbitrary graphs, the max-integral-flow / min-multicut ratio is O(ε^-1 log k), where k is the number of commodites; for graphs excluding a fixed subgraph as a minor (for instance, planar graphs), O(1 / ε); and, for dense graphs, O(1√ε). Our proofs are constructive in the sense that we give efficient algorithms which compute either an integral flow achieving the claimed approximation ratios, or a witness that the precondition is violated.