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.

Authors

• Kenji Obata

Keywords

No keywords are indexed for this paper.