Open Problem Garden

Definitions: Let be a directed graph. A directed cut of is an edge-cut in which all edges are directed the same way. A dijoin is a set of edges which intersect every directed cut.

There is an important theorem of Lucchesi and Younger [LY] which asserts that the dual problem has an optimum integer packing. That is, for every digraph in which the smallest dijoin has size , there exist pairwise disjoint directed cuts. This result implies more generally (in the terminology of Corneujols [C]) that the clutter of (minimal) directed cuts has the max-flow min-cut property (MFMC). It follows from this and Lehman's theorem [L] that the clutter of (minimal) dijoins is ideal. Therefore, if the smallest directed cut of has size , then there exist nonnegative rational numbers summing to and dijoins so that if each dijoin is taken with weight , the total weight of the dijoins containing any edge is at most 1. The above conjecture asserts that such a combination exists with integral.

Schrijver [Sc80] has found a digraph in which the clutter of (minimal) dijoins does not have the MFMC property. Thus, the weighted version of Woodall's conjecture is not true in general. However, this clutter does have the MFMC property in a number of interesting special cases. One such example (due to Schrijver [Sc82] and Feofiloff, Younger [FY]) is when the digraph is acyclic and every source is joined to every sink by a directed path. Since every such digraph has the MFMC property, every such digraph must satisfy Woodall's conjecture.

There seem to be few positive results towards Woodall's conjecture for general digraphs. Although this was probably already known, Seymour and I (M. DeVos) observed that the conjecture is true for . To see this, note that the underlying graph is 2-edge-connected, so it may be oriented to give a strongly connected digraph, call it . Now partition the edges into two sets where consists of those edges which have the same orientation in both and , and consists of those edges with different orientations in the two graphs. It is immediate that both and meet every directed cut, so each is a dijoin. Extending this to appears difficult. Indeed, I believe the following weak version of this is still open.

Conjecture   Prove that there exists a fixed integer so that every digraph with all directed cuts of size contains three pairwise disjoint dijoins.

The restriction of this conjecture to the special case of planar graphs is also open. Here we can use duality to restate the conjecture. Call a set of edges a feedback arc-set if intersects every directed cycle (or equivalently, is acyclic).

Conjecture   If is a planar digraph with all directed cycles of length , then contains pairwise disjoint feedback arc-sets.

The above conjecture is known to fail when the assumption of planarity is removed. On the other hand, it does hold for digraphs which are orientations of series-parallel graphs [LW]. It is also still open for .