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

• 成果类型: Article; Early Access
• 署名作者: Traub, Vera; Koch, Laura Vargas; Zenklusen, Rico
• 署名单位: Swiss Federal Institutes of Technology Domain; ETH Zurich; RWTH Aachen University; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610; 1436-4646
• DOI: 10.1007/s10107-026-02365-x
• 发表日期: 2026-07-22
• 关键词: Unsplittable flow; planar graphs; Combinatorial Optimization; Approximation algorithms; time

摘要

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.