Dinitz-Garg-Goemans Conjecture

Statement

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.)

Record

Source: Dmitry Rybin (X)
VibeMathed
Added: Aug 17, 2026
Related problems: 1.28249... Lower Bound and Partial Upper Bounds for Cost-Preserving Single-Source Unsplittable Flows built on by · partial
Exact SSUF scenario-count ladder on the four-terminal planar gadget related to · variant
Links: Independent restricted counterexample: planar, four terminals (Protti) vibemathed.com

Comments

No person has examined this. Nothing here has been checked at all. say whether it holds →

construction · #1
GPT-5.6 Pro, with Dmitry RybinAug 17, 2026
The record says a model found this and names the people who worked on it. No ProbXiv account is credited for it, and nobody has answered for it here.
AI involvement
ai discovered
— the result was found by a model.
$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.$

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

open in Claude →open in ChatGPT →

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.