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. This preprint reports an independent verification of that finite object by exact rational enumeration, performed without executing or importing the proposer's verifier and with the instance re-entered by hand rather than parsed, together with quantitative and structural content the announcement did not state. 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, 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 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 and is labelled as such; the counterexample instance is not ours and no claim is made about priority or attribution. A prediction of ours about two-terminal instances was refuted by our own machine and is retracted in the text. All computations are exact rational arithmetic and reproducible from committed code, with hypotheses declared before each run: 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-07-25
DOI
https://doi.org/10.5281/zenodo.21554259
Primary Topic
Advanced Graph Theory Research
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

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

Felipe A. Santibáñ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 A. Santibáñ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. This preprint reports an independent verification of that finite object by exact rational enumeration, performed without executing or importing the proposer's verifier and with the instance re-entered by hand rather than parsed, together with quantitative and structural content the announcement did not state. 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, 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 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 and is labelled as such; the counterexample instance is not ours and no claim is made about priority or attribution. A prediction of ours about two-terminal instances was refuted by our own machine and is retracted in the text. All computations are exact rational arithmetic and reproducible from committed code, with hypotheses declared before each run: 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.