Decision algorithms for unsplittable flow and the half-disjoint paths problem
Jon M. Kleinberg · 1998
We consider the bounded unsplittable flow problem: given terminal pairs in a network, with associated real-valued demands in the range [0,½], 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 ...