Tuesday, March 15, 3pm ET (*7pm* GMT, *8am* Wed NZDT)
Ahmad Abdi, LSE
On packing dijoins in digraphs and weighted digraphs

Abstract:

Let $D=(V,A)$ be a digraph. A dicut is the set of arcs in a cut where all the arcs cross in the same direction, and a dijoin is a set of arcs whose contraction makes $D$ strongly connected. It is known that every dicut and dijoin intersect. Suppose every dicut has size at least $k$.

Woodall’s Conjecture, an important open question in Combinatorial Optimization, states that there exist $k$ pairwise disjoint dijoins. We make a step towards resolving this conjecture by proving that $A$ can be decomposed into two sets $A_1$ and $A_2$, where $A_1$ is a dijoin, and $A_2$ intersects every dicut in at least $k-1$ arcs. We prove this by a Decompose, Lift, and Reduce (DLR) procedure, in which $D$ is turned into a sink-regular $(k,k+1)$-bipartite digraph. From there, by an application of Matroid Optimization tools, we prove the result.

The DLR procedure works more generally for weighted digraphs, and exposes an intriguing number-theoretic aspect of Woodall’s Conjecture. In fact, under natural number-theoretic conditions, Woodall’s Conjecture and a weighted extension of it are true. By pushing the barrier here, we expose strong base orderability as a key notion for tackling Woodall’s Conjecture.

Based on joint work with Gerard Cornuejols and Michael Zlatin.