Weaker variant of Woodall's dijoin decomposition conjecture

From papers

Let D=(V,A)D=(V,A) be a digraph, and let a dijoin be a set of arcs meeting every dicut. A set of arcs is a kk-dijoin if it can be decomposed into kk dijoins. Let τ2\tau\geq 2 be an integer, and suppose every dicut of DD has size at least τ\tau.

Weaker dijoin decomposition conjecture. The arc set AA can be decomposed into a kk-dijoin and a (τk)(\tau-k)-dijoin, for every k{1,,τ1}k\in\{1,\ldots,\tau-1\}.

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 k=1k=1 and k=τ1k=\tau-1 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

No solutions have been posted yet.