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
- Felipe Santibañ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-09-18
- DOI
- https://doi.org/10.5281/zenodo.21554258
- Primary Topic
- Advanced Graph Theory Research
- Type
- preprint