The ACO Seminar (2021–2022)

In any directed graph, the minimum size of a dijoin is equal to the maximum number of disjoint dicuts. This is the celebrated Luccesi-Younger theorem and is even known to hold in a weighted setting. However, by interchanging the roles of dicuts and dijoins, we obtain the much more mysterious Woodall's conjecture, which asks: If the minimum size of a dicut is k, are there always k pairwise disjoint dijoins? This beautiful min-max conjecture has remained open for 50 years with little recent progress. It is known to be false in the weighted setting, and is still open in various special cases, such as when k = 3, or when the digraph is planar. In this talk, I will discuss our recent progress towards Woodall's conjecture. We show that for the purposes of proving (or disproving) Woodall's conjecture, it suffices to consider only `bipartite' digraphs satisfying certain degree conditions. We use this to show that, in any optimal fractional packing, at least one dijoin can be chosen to have value 1. This talk is about joint work with Professors Ahmad Abdi and Gérard Cornuéjols.