Edmonds–Giles weighted dijoin packing conjecture
Edmonds–Giles weighted dijoin packing conjecture
Let be a digraph with arc weights . The weight of a dicut is the \sum of the weights of its arcs, and the minimum dicut weight is the smallest such weight. The digraph packs dijoins if it has dijoins such that no arc belongs to more than of them.
Edmonds–Giles conjecture. If the minimum weight of a dicut is , then can pack dijoins.
The conjecture was disproved by Schrijver, so the corresponding weighted packing assertion is false; its unweighted version is Woodall's still-open conjecture.
Sources & referencesView supporting material
Primary source
Gérard Cornuéjols, Siyue Liu and R. Ravi, “Approximately Packing Dijoins via Nowhere-Zero Flows”, arXiv:2311.04337 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.