Graphs and Matroids Seminar

Title: 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 A1 and A2, where A1 is a dijoin, and A2 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.