Dinitz–Garg–Goemans conjecture
In combinatorial optimization, the Dinitz–Garg–Goemans conjecture, also called Goemans' conjecture or the cost conjecture, is a statement about single-source unsplittable flows. It concerns the problem of converting a fractional flow, which may split each terminal's demand across several paths, into an unsplittable one, which routes each demand along a single path, without straying too far from the original. The conjecture asserts that given any fractional flow and any assignment of costs to the arcs, there is an unsplittable flow that exceeds the fractional flow on each arc by at most the maximum demand while costing no more than the fractional flow overall.
The conjecture strengthens the Dinitz–Garg–Goemans theorem, proved in 1999 by Yefim Dinitz, Naveen Garg, and Michel Goemans, which guarantees an unsplittable flow that exceeds a given fractional flow on each arc by at most the maximum demand. The conjecture went further, asking whether such a flow can additionally be required to cost no more than the fractional flow.
On July 22, 2026, mathematician Dmitry Rybin presented a counterexample in which a fractional flow of cost 58 exists, yet every unsplittable flow that meets the capacity bound costs at least 60 using GPT-5.6, a large language model by OpenAI. The disproof establishes that the theorem's capacity guarantee and a matching cost guarantee cannot always be achieved simultaneously by a single flow.