|
Discrete Mathematics and Optimization Seminar
|
Nov. 16th, 2009
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 K2,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.
|
|
|
|