Weaker variant of Woodall's dijoin decomposition conjecture
Let be a digraph, and let a dijoin be a set of arcs meeting every dicut. A set of arcs is a -dijoin if it can be decomposed into dijoins. Let be an integer, and suppose every dicut of has size at least .
Weaker dijoin decomposition conjecture. The arc set can be decomposed into a -dijoin and a -dijoin, for every .
This is presented as a weaker variant of Woodall's conjecture, which asserts that the minimum size of a dicut equals the maximum number of pairwise disjoint dijoins and remains open. The case and is known, while the intermediate cases remain open.
References
Primary source
Ahmad Abdi, Gérard Cornuéjols and Giacomo Zambelli, “Arc connectivity and submodular flows in digraphs”, arXiv:2310.19472 (2023).
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
No solutions have been posted yet.