Woodall's conjecture

In the mathematics of directed graphs, Woodall's conjecture is an unproven relationship between dicuts and dijoins. It was posed by Douglas Woodall in 1976.^[1]

Unsolved problem in mathematics

Does the minimum number of edges in a dicut of a directed graph always equal the maximum number of disjoint dijoins?

More unsolved problems in mathematics

Statement

A dicut is a partition of the vertices into two subsets such that all edges that cross the partition do so in the same direction. A dijoin is a subset of edges that, when contracted, produces a strongly connected graph; equivalently, it is a subset of edges that includes at least one edge from each dicut.^[2]

On the left, a dicut with the minimum number of edges for the given graph, that being 3 edges (in red), forming 2 partitions (the set of blue vertices, and the set of green). On the right, the same number of disjoint dijoins (each represented by a different color).

According to the Lucchesi-Younger theorem, if the minimum number of edges in a dicut is ${\displaystyle k}$, then there can be at most ${\displaystyle k}$ disjoint dijoins in the graph, because each one must include a different edge from the smallest dicut. Woodall's conjecture states that, in this case, it is always possible to find ${\displaystyle k}$ disjoint dijoins. That is, any directed graph the minimum number of edges in a dicut equals the maximum number of disjoint dijoins that can be found in the graph (a packing of dijoins).^[2][1]

Partial results

It is a folklore result that the theorem is true for directed graphs whose minimum dicut has two edges.^[2] Any instance of the problem can be reduced to a directed acyclic graph by taking the condensation of the instance, a graph formed by contracting each strongly connected component to a single vertex. Another class of graphs for which the theorem has been proven true are the directed acyclic graphs in which every source vertex (a vertex without incoming edges) has a path to every sink vertex (a vertex without outgoing edges).^[3][4]

Related results

A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver.^[5][6][2] In the other direction, the Lucchesi–Younger theorem states that the minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.^[7][8]