An independent exact verification of the 2026 counterexample to Goemans' unsplittable-flow cost conjecture, with the violation constant it forces

In July 2026 a counterexample to Goemans' cost version of the Dinitz–Garg–Goemans theorem was announced publicly, outside peer review, and circulated widely. We report an independent verification of that finite object by exact rational enumeration, performed without executing or importing the proposer's verifier, together with quantitative and structural content that the announcement did not state. Our results: (i) the instance is confirmed, so Goemans' conjecture is false, and, the instance being acyclic, the Morell–Skutella cost conjecture and the convex-combination form fall with it; (ii) the instance forces a violation of exactly 16/15 of the maximum demand d_max, that is, the conjecture fails by one unit at d_max = 15, so the open question whether cost-preserving rounding is possible with O(d_max) violation is untouched by it; (iii) every proved result in the area survives its direct test on the instance, including the Dinitz–Garg–Goemans theorem, the Morell–Skutella cost-free conjecture, the series-parallel theorem of Majthoub Almoghrabi, Skutella and Warode, and the planar theorem of Traub, Vargas Koch and Zenklusen; (iv) the instance contains a K4 subdivision, hence sits exactly one structure outside the series-parallel class where the conjecture is proved, and, being planar, pins the planar constant strictly between 1 and 2; (v) an exact separation linear program shows that the published cost vector is an optimal separator for that graph and fractional flow, so its cost gap cannot be improved by any reweighting; and (vi) a first minimality result, that no single-terminal instance is a counterexample for any nonnegative cost vector, together with a necessary condition at two terminals. The verification is a replication; items (ii) and (iv)-(vi) are, to our knowledge, new. The two-terminal case remains open, and we show why a natural argument for it fails. The counterexample instance is not ours, and no claim is made about priority or attribution. Source code, data and computational records: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/optimization-geometry/unsplittable-flow-cost).

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-09-18
DOI
https://doi.org/10.5281/zenodo.21554258
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
preprint

An independent exact verification of the 2026 counterexample to Goemans' unsplittable-flow cost conjecture, with the violation constant it forces

Felipe Santibañez-Leal
Zenodo (CERN European Organization for Nuclear Research)
Advanced Graph Theory Research
preprint

An independent exact verification of the 2026 counterexample to Goemans' unsplittable-flow cost conjecture, with the violation constant it forces

Felipe Santibañez-Leal
preprint en

Abstract

In July 2026 a counterexample to Goemans' cost version of the Dinitz–Garg–Goemans theorem was announced publicly, outside peer review, and circulated widely. We report an independent verification of that finite object by exact rational enumeration, performed without executing or importing the proposer's verifier, together with quantitative and structural content that the announcement did not state. Our results: (i) the instance is confirmed, so Goemans' conjecture is false, and, the instance being acyclic, the Morell–Skutella cost conjecture and the convex-combination form fall with it; (ii) the instance forces a violation of exactly 16/15 of the maximum demand d_max, that is, the conjecture fails by one unit at d_max = 15, so the open question whether cost-preserving rounding is possible with O(d_max) violation is untouched by it; (iii) every proved result in the area survives its direct test on the instance, including the Dinitz–Garg–Goemans theorem, the Morell–Skutella cost-free conjecture, the series-parallel theorem of Majthoub Almoghrabi, Skutella and Warode, and the planar theorem of Traub, Vargas Koch and Zenklusen; (iv) the instance contains a K4 subdivision, hence sits exactly one structure outside the series-parallel class where the conjecture is proved, and, being planar, pins the planar constant strictly between 1 and 2; (v) an exact separation linear program shows that the published cost vector is an optimal separator for that graph and fractional flow, so its cost gap cannot be improved by any reweighting; and (vi) a first minimality result, that no single-terminal instance is a counterexample for any nonnegative cost vector, together with a necessary condition at two terminals. The verification is a replication; items (ii) and (iv)-(vi) are, to our knowledge, new. The two-terminal case remains open, and we show why a natural argument for it fails. The counterexample instance is not ours, and no claim is made about priority or attribution. Source code, data and computational records: https://github.com/fsantibanezleal/CAOS_RESEARCH (problems/optimization-geometry/unsplittable-flow-cost).

Zenodo (CERN European Organization for Nuclear Research)
Open University of Cyprus (CY)
Peace, Justice and strong institutions
Advanced Graph Theory Research
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.