Woodall's conjecture

Last updated
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

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]

Contents

Statement

A dicut is a set of edges defined from 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). Woodall.png
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 , then there can be at most 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 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]

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]

References

  1. 1 2 Woodall, D. R. (1978), "Menger and König systems", in Alavi, Yousef; Lick, Don R. (eds.), Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Mathematics, vol. 642, Berlin: Springer, pp. 620–635, doi:10.1007/BFb0070416, MR   0499529
  2. 1 2 3 4 Abdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv: 2202.00392
  3. ↑ Schrijver, A. (1982), "Min-max relations for directed graphs", Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Annals of Discrete Mathematics, vol. 16, North-Holland, pp. 261–280, MR   0686312
  4. ↑ Feofiloff, P.; Younger, D. H. (1987), "Directed cut transversal packing for source-sink connected graphs", Combinatorica , 7 (3): 255–263, doi:10.1007/BF02579302, MR   0918396
  5. ↑ Edmonds, Jack; Giles, Rick (1977), "A min-max relation for submodular functions on graphs", Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, vol. 1, North-Holland, Amsterdam, pp. 185–204, MR   0460169
  6. ↑ Schrijver, A. (1980), Bachem, Achim; Grötschel, Martin; Korte, Bernhard (eds.), "A counterexample to a conjecture of Edmonds and Giles" (PDF), Discrete Mathematics , 32 (2): 213–215, doi: 10.1016/0012-365X(80)90057-6 , MR   0592858
  7. ↑ Lovász, László (1976), "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B, 21 (2): 96–103, doi: 10.1016/0095-8956(76)90049-6 , MR   0427138
  8. ↑ Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 369–374, doi:10.1112/jlms/s2-17.3.369, MR   0500618
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.