A Planar Lower Bound 1.1397... > 9/8 for Cost-Preserving Single-Source Unsplittable Flows

For a single-source unsplittable flow, consider rounding a feasible fractional flow $\textbf{x}$ to one path per terminal while requiring both the cost constraint $\textbf{c}^\top\textbf{y}\le\textbf{c}^\top\textbf{x}$ and the overload constraint $y_a\le x_a+Cd_{\max}$ on every arc. Dinitz, Garg and Goemans proved that the congestion bound alone is achievable with $C=1$; Goemans conjectured that cost preservation comes for free, and this was disproved in July 2026 by a seven-vertex instance with critical constant 16/15. We give a four-terminal planar acyclic family showing that every universal constant C in the overload constraint must satisfy$$ C\ \ge\ C^\star:=\frac{299-41\sqrt{41}}{32}\ =\ 1.139747070789\ldots\ >\ \frac98 .$$ The construction is a directed spine with two private exits per terminal and exactly two simple source-terminal paths for each terminal. An integer one-parameter subfamily has exact critical constant $\frac{182359}{160000}-\frac 1n$, which is larger than $\frac98$ for $n\ge68$. We also prove that $9/8$ is the exact supremum of the three-terminal template underlying the known counterexample, so a different conflict system was needed; indeed, our new counterexample places four crossing intervals on a spine and drives the conflicts through the unavoidable baseline loads of the expensive routes. The graph is small and the results are easy to verify by hand, but we additionally certify all our claims in exact rational or symbolic arithmetic by programs that rediscover all simple source-terminal paths from the raw arc list; we make the certificate programs available at https://github.com/snikolenko/unsplittable-flows. We conjecture that the exact supremum of forced constants is $2$, and record some structural questions that stand between $C^\star$ and $2$.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-07-30
DOI
https://doi.org/10.5281/zenodo.21701162
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

A Planar Lower Bound 1.1397... > 9/8 for Cost-Preserving Single-Source Unsplittable Flows

Sergey Nikolenko
Zenodo (CERN European Organization for Nuclear Research)
Complexity and Algorithms in Graphs
preprint

A Planar Lower Bound 1.1397... > 9/8 for Cost-Preserving Single-Source Unsplittable Flows

Sergey Nikolenko
preprint en

Abstract

For a single-source unsplittable flow, consider rounding a feasible fractional flow $\textbf{x}$ to one path per terminal while requiring both the cost constraint $\textbf{c}^\top\textbf{y}\le\textbf{c}^\top\textbf{x}$ and the overload constraint $y_a\le x_a+Cd_{\max}$ on every arc. Dinitz, Garg and Goemans proved that the congestion bound alone is achievable with $C=1$; Goemans conjectured that cost preservation comes for free, and this was disproved in July 2026 by a seven-vertex instance with critical constant 16/15. We give a four-terminal planar acyclic family showing that every universal constant C in the overload constraint must satisfy$$ C\ \ge\ C^\star:=\frac{299-41\sqrt{41}}{32}\ =\ 1.139747070789\ldots\ >\ \frac98 .$$ The construction is a directed spine with two private exits per terminal and exactly two simple source-terminal paths for each terminal. An integer one-parameter subfamily has exact critical constant $\frac{182359}{160000}-\frac 1n$, which is larger than $\frac98$ for $n\ge68$. We also prove that $9/8$ is the exact supremum of the three-terminal template underlying the known counterexample, so a different conflict system was needed; indeed, our new counterexample places four crossing intervals on a spine and drives the conflicts through the unavoidable baseline loads of the expensive routes. The graph is small and the results are easy to verify by hand, but we additionally certify all our claims in exact rational or symbolic arithmetic by programs that rediscover all simple source-terminal paths from the raw arc list; we make the certificate programs available at https://github.com/snikolenko/unsplittable-flows. We conjecture that the exact supremum of forced constants is $2$, and record some structural questions that stand between $C^\star$ and $2$.

Zenodo (CERN European Organization for Nuclear Research)
St. Petersburg Department of Steklov Institute of Mathematics (RU)
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.