|
Abstract : |
We consider the bounded unsplittable flow problem: given terminal pairs in a network, with associated real-valued demands in the range [0; 1 2], find a single flow path for each pair so that no more than 1 unit of demand is routed through any vertex. Thus, the setting is not directly comparable to that of the classical disjoint paths problem (when all demands are equal to 1)---we must deal with connections having varied, real-valued amounts of demand, but we impose the boundedness restriction that each connection can consume at most half the capacity of any vertex. Our main result is a polynomial-time algorithm for the bounded unsplittable flow problem, in an arbitrary graph, when the number of terminal pairs is a fixed constant. Our algorithm is conceptually much simpler than Robertson and Seymour's corresponding algorithm for the disjoint paths problem with a constant number of terminal pairs; and we can decide the routability of a non-trivially super-constant number of terminal pairs (up to\Omega\Gamma/383 log n), |
