Weaker variant of Woodall's dijoin decomposition conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Ahmad Abdi, Gérard Cornuéjols and Giacomo Zambelli, “Arc connectivity and submodular flows in digraphs”, arXiv:2310.19472 (2023).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.