
Discrete Mathematics and Optimization Seminar

Nov. 16th, 2009
FlowCut 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 flowcut 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
wellknown that the flowcut gap may be greater than 1 even in the
case where G is the (seriesparallel) graph K_{2,3}.
The subject of this talk is the "integer" flowcut 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 seriesparallel
graphs. Let G be obtained by seriesparallel 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 OkamuraSeymour
theorem. We use this to prove that the integer flowcut gap in
seriesparallel graphs is 5.



