Does the minimum number of edges in a dicut of a directed graph always equal the maximum number of disjoint dijoins?
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 edit
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 , 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 edit
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 edit
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 edit
- ^ a b 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
- ^ a b c d Abdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv:2202.00392
- ^ 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
- ^ 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
- ^ 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
- ^ 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
- ^ 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
- ^ 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
External links edit
- Feofiloff, Paulo (November 30, 2005), Woodall’s conjecture on Packing Dijoins: a survey (PDF)
- "Woodall's conjecture", Open Problem Garden, April 5, 2007