Theoretical computer science · Jul 22, 2026
Dinitz–Garg–Goemans flow conjecture
A seven-vertex, nine-arc witness: fractional cost 58; every allowed unsplittable routing costs at least 60, with demands 15,10,15.
Scope and what remains
Preserve the exact capacity augmentation, cost and demand model. Registry observation dates need not equal discovery or formalization dates.
Contributors
Dmitry Rybin and GPT-5.6 Pro for discovery; Arthur Freitas Ramos, David Barros Hulak and Ruy José Guerra Barreto de Queiroz for the independent Isabelle/HOL formalization.
AI systems: GPT-5.6 Pro