Single-source unsplittable flows in planar and bounded-genus graphs

Abstract

The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to terminals with unrelated demands, each terminal being served through a single path. The classical SSUF objective is to minimize the violation of some given arc capacities. A seminal result of Dinitz, Garg, and Goemans showed that, whenever a fractional flow exists respecting the capacities, then there is an unsplittable one violating the capacities by at most the maximum demand. Goemans conjectured a natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. Intriguingly, there are arguably no non-trivial graph classes for which it is known to hold. We show that a slight weakening of it holds for planar graphs, by exploiting a connection to a highly structured discrepancy problem. Moreover, our techniques extend to simultaneous upper and lower bounds on the flow values. This affirmatively answers a conjecture of Morell and Skutella for planar SSUF. Finally, we show that our approach can be extended to general (non-planar) graphs with a capacity violation that depends on the genus.