The flow/cut gap for multicommodity flows in series-parallel graphs<BR>

<p>
Christophe Weibel, McGill University<BR>

<P>
Abstract:<BR>
In multicommodity flows, the max-flow/min-cut gap is the ratio between the edge capacity necessary to route every demand and the capacity verifying the cut condition. In the case of splittable flows, it was recently proved that the gap can be at most 2 for series-parallel graphs. In the case of unsplittable flows, we prove an upper bound of 5 for the same series-parallel graphs. We also conjecture, and show some evidence, that the actual upper bound is 2 as in splittable flows.