Unsplittable Multicommodity Flows

Abstract

An instance (G,u,H,d) of multicommodity flow is given by an undirected graph G=( V, E(G) ) with edge capacities u: E(G)→ℝ, and a collection of source-sink pairs (s_i,t_i) in V with associated nonnegative demands d(s_i, t_i). It will be convenient to think of the source-sink pairs as forming the edges of a demand graph H=( V, E(H) ). The problem is to determine the existence of a flow x that routes all the demands and that does not violate the edge capacity constraints, i.e., x(e) ≤ u(e) for all e ∈ E(G). An instance is feasible if such a flow exists. In the standard multicommodity flow setting, the demand between a source-sink pair may be split across multiple paths.

In this thesis we focus mainly on two classes of instances for which feasibility has a nice characterization, the cut-condition: for every cut, the total demand crossing the cut is at most the total capacity of the edges crossing it.

Okamura and Seymour showed that the cut-condition is sufficient for routing demands in outerplanar graphs. Seymour showed that the same result holds when G+H is planar.

We study the unsplittable version of the problem and prove that, if the cut-condition is satisfied for either of these two classes, then each demand can be routed along a single path while exceeding the capacity of any edge by at most an additive amount of 2Dmax, where Dmax denotes the maximum demand value. We also show that both of these results are almost tight.