Edmonds–Giles weighted dijoin packing conjecture

Let D=(V,A)D=(V,A) be a digraph with arc weights wi{0,1}Aw i\{0,1\}^A. 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 kk dijoins if it has kk dijoins such that no arc ee belongs to more than w(e)w(e) of them.

Edmonds–Giles conjecture. If the minimum weight of a dicut is τ\tau, then DD can pack τ\tau 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.