Flows on Few Paths: Algorithms and Lower Bounds

In classical network flow theory, flow being sent from a source to a destination may be split into a large number of chunks traveling on different paths through the network. This effect is undesired or even forbidden in many applications. Kleinberg introduced the unsplittable flow problem where all flow traveling from a source to a destination must be sent on only one path. This is a generalization of the NP-complete edge-disjoint paths problem. In particular, the randomized rounding technique of Raghavan and Thompson can be applied. A generalization of unsplittable flows are k-splittable flows where the number of paths used by a commodity i is bounded by a given integer k i .