Scholarlink

<p>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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月22日

查看全文
  • Vera Traub,
  • Laura Vargas Koch,
  • Rico Zenklusen

摘要

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.