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
- Felipe A. Santibáñez-Leal (ORCID: https://orcid.org/0000-0002-0150-3246)
Institutions
- Open University of Cyprus (CY)
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