Dinitz-Garg-Goemans Conjecture
For single-source unsplittable flow, every fractional flow can be rounded to an unsplittable flow whose cost is no higher than the fractional cost, while each arc's load is exceeded by at most the maximum demand. (The cost version of Goemans' unsplittable-flow conjecture.)
- Result
- Disproved
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Combinatorial Optimization
- Posed by
- Yefim Dinitz, Naveen Garg, Michel Goemans
- Year posed
- 1999
- Years open
- 27y
- Solved
- 2026-07-22
- Model
- GPT-5.6 Pro
- Vendor
- OpenAI
- Collaborators
- Dmitry Rybin
- Verification
- Unreviewed
- Publication
- Announced
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- Not counted (article postdates the solution)
What the AI did
Rybin used GPT-5.6 Pro to search for and construct an explicit counterexample: a graph whose fractional flow cost is 58, while every unsplittable flow with capacity violation at most 15 costs at least 60 - so no cost-preserving rounding exists.
Verification
Announced on X by Dmitry Rybin (2026-07-22) with a shared GPT-5.6 Pro chat. The counterexample is a concrete finite graph checkable by direct computation (fractional cost 58 vs. minimum unsplittable cost 60 under capacity violation ), but it is not yet peer-reviewed or formally verified. Not to be confused with the separate 'Dinitz conjecture' on Latin-square colourings.
Sources
Related entries
- Built on byCommon-Point Interval Systems for SSUF
- RelatedFour-terminal SSUF scenario ladder