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.
Single-source unsplittable flow A single-source unsplittable flow (SSUF) instance consists of a directed graph G = ( V , A ) {\displaystyle G=(V,A)} with a distinguished source s ∈ V {\displaystyle s\in V} , a set of terminals T ⊆ V {\displaystyle T\subseteq V} with associated demands d t ≥ 0 {\displaystyle d_{t}\geq 0} for each t ∈ T {\displaystyle t\in T} , and nonnegative arc capacities u a {\displaystyle u_{a}} for each a ∈ A {\displaystyle a\in A} . A splittable (or fractional) flow x {\displaystyle x} routes d t {\displaystyle d_{t}} units from s {\displaystyle s} to each terminal t {\displaystyle t} subject to flow conservation, possibly dividing each demand over several paths. A flow is unsplittable if the entire demand d t {\displaystyle d_{t}} of each terminal travels along a single s {\displaystyle s} – t {\displaystyle t} path; equivalently, one chooses one path per terminal, and the flow on an arc is the sum of the demands whose paths use that arc. Deciding whether an unsplittable flow respecting all capacities exists is NP-hard, which motivates studying unsplittable flows that only approximately respect the capacities or that stay close to a given fractional flow.
The Dinitz–Garg–Goemans theorem Let d max = max t ∈ T d t {\displaystyle d_{\max }=\max _{t\in T}d_{t}} denote the largest demand. Dinitz, Garg, and Goemans proved that, given any fractional flow x {\displaystyle x} satisfying the demands, there exists an unsplittable flow y {\displaystyle y} satisfying the same demands such that
y a ≤ x a + d max for every arc a ∈ A . {\displaystyle y_{a}\leq x_{a}+d_{\max }\qquad {\text{for every arc }}a\in A.}
In words, the unsplittable flow exceeds the given flow on each arc by at most the maximum demand. As a consequence, if all capacities are at least d max {\displaystyle d_{\max }} , one obtains an unsplittable flow with congestion at most 2, which is best possible. A short one-page proof and a matching lower-bound analogue, y a ≥ x a − d max {\displaystyle y_{a}\geq x_{a}-d_{\max }} , were later given by Sarah Morell and Martin Skutella.
Statement of the conjecture Suppose each arc a {\displaystyle a} additionally carries a nonnegative cost c a {\displaystyle c_{a}} . Goemans conjectured that the unsplittable flow can be found so as to both respect the additive capacity bound and cost no more than the fractional flow. Formally, for every SSUF instance, every fractional flow x {\displaystyle x} , and every cost vector c ≥ 0 {\displaystyle c\geq 0} , there exists an unsplittable flow y {\displaystyle y} such that
y a ≤ x a + d max for all a ∈ A , and ∑ a ∈ A c a y a ≤ ∑ a ∈ A c a x a . {\displaystyle y_{a}\leq x_{a}+d_{\max }\quad {\text{for all }}a\in A,\qquad {\text{and}}\qquad \sum _{a\in A}c_{a}\,y_{a}\;\leq \;\sum _{a\in A}c_{a}\,x_{a}.}
The theorem of Dinitz, Garg, and Goemans establishes the first condition alone. The conjecture is that the two can be achieved simultaneously. Morell and Skutella proposed a still stronger, two-sided form, conjecturing the existence of an unsplittable flow y {\displaystyle y} with
x a − d max ≤ y a ≤ x a + d max for all a ∈ A , {\displaystyle x_{a}-d_{\max }\;\leq \;y_{a}\;\leq \;x_{a}+d_{\max }\qquad {\text{for all }}a\in A,}
which implies Goemans' cost version. A related formulation, going back to Goemans, asks whether every fractional flow is a convex combination of unsplittable flows each obeying the additive bound.
Partial results For a long time the conjecture was not known to hold for any non-trivial class of graphs. Vera Traub, Laura Vargas Koch, and Rico Zenklusen established a weakening for planar graphs, in which the permitted capacity violation is at most doubled. In 2025, Mohammed Majthoub Almoghrabi, Skutella, and Philipp Warode proved both Goemans' conjecture and the stronger Morell–Skutella conjecture for series–parallel graphs, the first non-trivial graph class for which either was confirmed, even in the more general setting of multiple sources and sinks.
Counterexample On 22 July 2026, the mathematician Dmitry Rybin announced on the social platform X that the conjecture is false, stating that he had found a counterexample with the assistance of the large language model GPT-5.6 Pro. According to the announcement, the graph admits a fractional flow of cost 58, whereas every unsplittable flow whose capacity violation is at most 15 has cost at least 60, thereby exceeding the fractional optimum and contradicting the cost conjecture.
References