Weaker variant of Woodall's dijoin decomposition conjecture

About 3 years old · traced to

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.

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

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.