MathDB
← All problems

Dinitz–Garg–Goemans conjecture

27 years old · traced to

Let G=(V,A)G=(V,A) be a directed graph with a distinguished source s∈Vs\in V, a set of terminals T⊆VT\subseteq V, and a demand dt≥0d_t\geq 0 for each t∈Tt\in T. A flow x=(xa)a∈Ax=(x_a)_{a\in A} with xa≥0x_a\geq 0 is called feasible (splittable, or fractional) for this instance if it satisfies flow conservation and routes dtd_t units from ss to tt for every t∈Tt\in T simultaneously; that is, xx is a nonnegative combination of ss–tt path flows whose total value into each terminal tt equals dtd_t, with each demand possibly divided among several paths. A flow yy is called unsplittable if there is a choice of a single ss–tt path PtP_t for each t∈Tt\in T such that

ya=∑t∈T: a∈Ptdtfor every a∈A,y_a=\sum_{t\in T:\ a\in P_t} d_t \qquad \text{for every } a\in A,

so that the entire demand of each terminal travels along one path. Put dmax⁡=max⁡t∈Tdtd_{\max}=\max_{t\in T} d_t.

For every such instance, every fractional flow xx feasible for it, and every cost vector c=(ca)a∈Ac=(c_a)_{a\in A} with ca≥0c_a\geq 0 for all a∈Aa\in A, there \exists an unsplittable flow yy satisfying the same demands such that

ya≤xa+dmax⁡for all a∈A,and∑a∈Aca ya  ≤  ∑a∈Aca xa.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.
Equivalent formulations

  1. Can every fractional single-source unsplittable flow be rounded without increasing either edge congestion or total cost?

References
  1. Wikipedia, Dinitz–Garg–Goemans conjecture, the article this problem comes from.

Source: Wikipedia

graph-theoryunsolved-problem
Posted · edited

Progress summary

Refreshed
Open · solution reported

A computer-assisted counterexample was announced in July 2026, but it has not been independently verified, so the conjecture is not settled.

The conjecture, dating from roughly 1999, asks whether fractional single-source unsplittable flows can be rounded while preserving both congestion increase at most dmax⁡d_{\max} and total cost. Dinitz, Garg, and Goemans proved the congestion-only guarantee; Goemans formulated the cost-preserving strengthening.

Known results

  • Dinitz, Garg, and Goemans: congestion at most xa+dmax⁡x_a+d_{\max} on every arc.
  • Morell and Skutella: the matching lower bound ya≥xa−dmax⁡y_a\ge x_a-d_{\max} and a stronger two-sided conjecture.
  • Traub, Vargas Koch, and Zenklusen: a planar weakening with congestion violation at most 2dmax⁡2d_{\max}.
  • Almoghrabi, Skutella, and Warode, 2025: both conjectures proved for series–parallel graphs, including multiple sources and sinks.

July 2026 claimed counterexample

Dmitry Rybin, assisted by GPT-5.6 Pro, reported a seven-node instance with fractional cost 5858, while every unsplittable flow obeying the dmax⁡=15d_{\max}=15 congestion allowance has cost at least 6060. The claim includes proof certificates and exhaustive enumeration, but is not peer-reviewed or independently verified.

Current status (as of July 2026): the general conjecture has a reported counterexample, but no independently verified disproof; the series–parallel and planar variants remain the strongest established results described here.

Sources

Solutions 0

No solutions have been posted yet.