In any digraph, the minimum size of a dicut equals the maximum number of disjoint dijoins.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Statement
In every digraph, the minimum cardinality of a directed cut equals the maximum number of pairwise disjoint dijoins (Woodall).
Assessment
Renown 3/5
A central min-max conjecture in combinatorial optimization, dual to the Lucchesi-Younger theorem.
Attackability 2/5
Finite digraph witness, LP-checkable; known hard instances (Schrijver's examples) seed the boundary, but the k=2 case alone has resisted for decades.
- finite witness
- 5/5
- oracle cost
- 3/5
- freshness
- 1/5
- seedability
- 3/5
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
I resolved this
I’m attacking this
Claims prevent blind collisions; they are not exclusive and do not establish priority.