Woodall's conjecture
 |
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]
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]
If the minimum number of edges in a dicut is [math]\displaystyle{ k }[/math], then there can be at most [math]\displaystyle{ k }[/math] 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 [math]\displaystyle{ k }[/math] 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]
References
- ↑ 1.0 1.1 Woodall, D. R. (1978), "Menger and König systems", in Alavi, Yousef; Lick, Don R., Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Mathematics, 642, Berlin: Springer, pp. 620–635, doi:10.1007/BFb0070416
- ↑ 2.0 2.1 2.2 2.3 Abdi, Ahmad (2022), On packing dijoins in digraphs and weighted digraphs
- ↑ Schrijver, A. (1982), "Min-max relations for directed graphs", Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Annals of Discrete Mathematics, 16, North-Holland, pp. 261–280
- ↑ Feofiloff, P.; Younger, D. H. (1987), "Directed cut transversal packing for source-sink connected graphs", Combinatorica 7 (3): 255–263, doi:10.1007/BF02579302
- ↑ "A min-max relation for submodular functions on graphs", Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, 1, North-Holland, Amsterdam, 1977, pp. 185–204
- ↑ Bachem, Achim; Grötschel, Martin; Korte, Bernhard, eds. (1980), "A counterexample to a conjecture of Edmonds and Giles", Discrete Mathematics 32 (2): 213–215, doi:10.1016/0012-365X(80)90057-6
- ↑ "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B 21 (2): 96–103, 1976, doi:10.1016/0095-8956(76)90049-6
- ↑ 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
External links
- Feofiloff, Paulo (November 30, 2005), Woodall’s conjecture on Packing Dijoins: a survey, https://www.ime.usp.br/~pf/dijoins/woodall/survey1-en.pdf
- "Woodall's conjecture", Open Problem Garden, April 5, 2007, http://garden.irmacs.sfu.ca/?q=op/woodalls_conjecture
 |  |
