Pinning on Tight Cuts: Improved Algorithm and Bounds for Unsplittable Multicommodity Flows in Outerplanar Graphs

The multicommodity flow problem in an undirected capacitated graph G is specified by a set of source-sink pairs with nonnegative demands. A flow is feasible if it routes all demands without exceeding the edge capacities, and it is unsplittable if it routes each demand along a single path. Let α be the smallest value such that the existence of a feasible flow implies the existence of an unsplittable flow that exceeds the edge capacities by at most + α d_max. Schrijver, Seymour, and Winkler showed that α ∈ [1.01, 1.5] if G is a cycle. These bounds were ultimately improved to α ∈ [1.1, 1.3] by Skutella and Däubel. Recently, Alemán Espinosa and Kumar extended this constant upper bound to the broader class of outerplanar graphs, and showed that if G is outerplanar then α ≤ 3.6. We show that α ∈ [4/3,2] if G is outerplanar. We introduce a novel technique that considers the global parameters of the instance, and that may be useful in other (more general) settings where the cut-condition is sufficient, or nearly sufficient, for the existence of a feasible flow.