Single-Source Unsplittable Flow

The max-flow min-cut theorem of Ford and Fulkerson is based on an even more foundational result, namely Menger's theorem on graph connectivity. Menger's theorem provides a good characterization for the following single-source disjoint paths problem: given a graph G, with a source vertex s and terminals t 1 , ..., t k , decide whether there exist edge-disjoint s-t i paths, for i = 1, ..., k. We consider a natural, NP-hard generalization of this problem, which we call the single-source unsplittable flow problem. We are given a source and terminals as before; but now each terminal t i has a demand ae i 1, and each edge e of G has a capacity c e 1. The problem is to decide whether one can choose a single s-t i path, for each i, so that the resulting set of paths respects the capacity constraints --- the total amount of demand routed across any edge e must be bounded by the capacity c e . The main results of this paper are constant-factor approximation algorithms for three n..