Single-Source Unsplittable Flows in Planar Graphs
Vera Traub, Laura Vargas Koch, Rico Zenklusen
Abstract
The single-source unsplittable flow (SSUF) problem asks to send flow from a common source to different terminals with unrelated demands, each terminal being served through a single path. One of the most heavily studied SSUF objectives 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 very natural cost version of the same result, where the unsplittable flow is required to be no more expensive than the fractional one. This intriguing conjecture remains open. More so, there are arguably no non-trivial graph classes for which it is known to hold.
We show that a slight weakening of it (with at most twice as large violations) holds for planar graphs. Our result is based on a connection to a highly structured discrepancy problem, whose repeated resolution allows us to successively reduce the number of paths used for each terminal, until we obtain an unsplittable flow. Moreover, our techniques also extend to simultaneous upper and lower bounds on the flow values. This also affirmatively answers a conjecture of Morell and Skutella for planar SSUF.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Lineage
Builds on2
Related papers
- Unsplittable Flow Cut Gap in Undirected GraphsDavid Alemán Espinosa, Nikhil Kumar, Joseph Poremba, F. Bruce ShepherdSODA 2026 · 1 citation
- Nested Dissection Meets IPMs: Planar Min-Cost Flow in Nearly-Linear TimeSally Dong, Yu Gao, Gramoz Goranci, Yin Tat Lee et al.SODA 2022 · 3 citations
- A face cover perspective to ℓ1 embeddings of planar graphsArnold FiltserSODA 2020 · 7 citations
- An Approximate Generalization of the Okamura-Seymour TheoremNikhil KumarFOCS 2022 · 1 citation
- Max s, t-Flow Oracles and Negative Cycle Detection in Planar DigraphsAdam KarczmarzSODA 2024 · 1 citation
