Conjecture · version 2
Every feasible fractional single-source flow x with nonnegative rational costs admits an unsplittable routing P with load_P(a) ≤ x(a) + d_max on every arc and total cost at most the cost of x.
Goemans’ cost-enhanced assertion is refuted; the original congestion-only theorem is not.
Disproved
The conjunction of a largest-demand congestion allowance and preservation of fractional cost.
Source dated Jul 22, 2026 · Observed Oct 13, 2026
Replaces an earlier source assessment. Version history ↓
Complete formal proof reported externally
The finite path-flow model is realized as the directed network earlier in the theory. This corollary proves the negation of cost-preserving rounding with the non-strict largest-demand allowance; it does not prove the positive conjecture.
Statement match: Linked by OpenMath · independent review separate · checked Oct 13, 2026
Dinitz_Garg_Goemans_Counterexample.weak_dgg_cost_conjecture_falseCommit 80985fd56a4cb63a90176bf4bfe456eaff949bfd
Complete formal proof reported externally
This declaration proves the negation of the positive conjecture above, over ℚ. Its name denotes a refutation, not a proof of the conjecture. The repository separately supplies a real-coefficient refutation. Planarity is discussed in the README and is not part of its formal statement.
Statement match: Linked by OpenMath · independent review separate · checked Oct 13, 2026
Submission.goemans_cost_conjecture_falseCommit ffba3523f0edd14be3460d039f22a6b98c02fd9e
In this problem · publication v9
Primary formulation · Disproved
Relationship not independently reviewed. This concerns its use in this problem.
A directed seven-vertex, nine-arc instance has fractional cost 58 and no congestion-allowed unsplittable routing of cost below 60.
paraphrase · OpenMath supplies its own mathematical paraphrases and links; proof text is not republished.
Arthur Freitas Ramos · David Barros Hulak · Ruy Jose Guerra Barretto de Queiroz · Published · Publication date Jul 22, 2026
Public formal source; execution and statement correspondence are separate checks.
Exact proof source inspected. This digest identifies this file only, not a project build, theorem correspondence or independent reproduction.
Source revision: 80985fd56a4cb63a90176bf4bfe456eaff949bfd. Observed Oct 13, 2026.
The AFP authors credit AI assistance for proof engineering and attribute the July counterexample announcement to Dmitry Rybin.
Cost-counterexample Isabelle theory: 80985fd56a4cb63a90176bf4bfe456eaff949bfd.
The project verifies the rational and real cost conjecture refutations and exact optimum 60 for the displayed instance.
paraphrase · OpenMath supplies its own mathematical paraphrases and links; proof text is not republished.
Jason Hickey · Project documentation · Publication date Aug 1, 2026
Public formal source; execution and statement correspondence are separate checks.
Exact proof source inspected. This digest identifies this file only, not a project build, theorem correspondence or independent reproduction.
Source revision: ffba3523f0edd14be3460d039f22a6b98c02fd9e. Observed Oct 13, 2026.
Jason Hickey credits Claude for the verification work and credits Dmitry Rybin’s GPT-5.6 Pro session for the original counterexample.
Cost-counterexample Lean submission: ffba3523f0edd14be3460d039f22a6b98c02fd9e.
The paper states the original congestion theorem, Goemans’ cost-enhanced conjecture and a planar theorem with twice the largest-demand allowance.
paraphrase · OpenMath supplies its own mathematical paraphrases and links; proof text is not republished.
Vera Traub · Laura Vargas Koch · Rico Zenklusen · Preprint · Publication date Aug 4, 2023
Source revision: 2023-08-04. Observed Oct 13, 2026.
No specific AI contribution is attributed by this source record.
Statement versions and problem publication versions are separate. A new publication can update context or sources while retaining the same statement.
Assessments retained in these publication records. Earlier statement versions retain their own source histories.
Disproved
The conjunction of a largest-demand congestion allowance and preservation of fractional cost.
Source dated Jul 22, 2026 · Observed Oct 13, 2026 · Source passage →
Replaces an earlier source assessment; see the original source for its history.