2023/11/07 by Cornuéjols, Gérard, Liu, Siyue, Ravi, R.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2311.04337
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. However, prior to our work, it was not even known whether at least 3 disjoint dijoins exist in an arbitrary digraph whose minimum dicut size is sufficiently large. By building connections with nowhere-zero (circular) k-flows, we prove that every digraph with minimum dicut size τ contains \lfloor\fracτk\rfloor disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) k-flow. The existence of nowhere-zero 6-flows in 2-edge-connected graphs (Seymour 1981) directly leads to the existence of \lfloor\fracτ6\rfloor disjoint dijoins in a digraph with minimum dicut size τ, which can be found in polynomial time as well. The existence of nowhere-zero circular (2p+1)/(p)-flows in 6p-edge-connected graphs (Lovász et al. 2013) directly leads to the existence of \lfloor(τp)/(2p+1)\rfloor disjoint dijoins in a digraph with minimum dicut size τ whose underlying undirected graph is 6p-edge-connected. We also discuss reformulations of Woodall's conjecture into packing strongly connected orientations.