DMO Seminar

Flow-Cut Gaps for Integer and Fractional Multiflows

Christophe Weibel

McGill University

Consider a routing problem instance consisting of a supply graph G=(V,E(G)) and a demand graph H=(V,E(H)). If the pair obeys the cut condition, then the flow-cut gap for this instance is the minimum value C such that there exists a feasible multiflow for H if each edge of G is given capacity C. It is well-known that the flow-cut gap may be greater than 1 even in the case where G is the (series-parallel) graph K_2,3.

The subject of this talk is the "integer" flow-cut gap. What is the minimum value C such that there exists a feasible integer valued multiflow for H if each edge of G is given capacity C? We study the case of series-parallel graphs. Let G be obtained by series-parallel operations starting from an edge st, and consider orienting all edges in G in the direction from s to t. A demand is compliant if its endpoints are joined by a directed path in the resulting oriented graph. We show that if the cut condition holds for a compliant instance and G+H is Eulerian, then an integral routing of H exists. This result includes, as a special case, routing on a ring, but is not a special case of the Okamura-Seymour theorem. We use this to prove that the integer flow-cut gap in series-parallel graphs is 5.