Approximately Packing Dijoins Via Nowhere-Zero Flows

In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. By building connections with nowhere-zero k-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\lfloor \tau/k \rfloor$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero k-flow.

Joint work with Gérard Cornuéjols (CMU) and Siyue Liu (CMU)