In mathematics, a dicut is a partition of the vertices of a directed graph into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Each

strongly connected component In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...

of the graph must be entirely contained in one of the two subsets, so a

strongly connected graph In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex. The strongly connected components of an arbitrary directed graph form a partition into subgraphs that a ...

has no nontrivial dicuts. The second of the two subsets in a dicut, a subset of vertices with no edges that exit the subset, is called a closure. The closure problem is the algorithmic problem of finding a dicut, in an edge-weighted directed graph, whose total weight is as large as possible. It can be solved in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

. In

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross ...

s, dicuts and cycles are dual concepts. The dual graph of a directed graph, embedded in the plane, is a graph with a vertex for each face of the given graph, and a dual edge between two dual vertices when the corresponding two faces are separated by an edge. Each dual edge crosses one of the original graph edges, turned by 90° clockwise. For a dicut in the given graph, the duals of the edges that cross the dicut form a directed cycle in the dual graph, and vice versa. A

dijoin In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph. Equivalently, a dijoin is a subset of the edges that, for every dicut, inclu ...

can be defined as a set of edges that crosses all dicuts; when the edges of a dijoin are contracted, the result is a strongly connected graph.

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. Statement A dicut is a partition of the vertices into two subsets such that all edges tha ...

, an unsolved problem in this area, states that in any directed graph the minimum number of edges in a dicut (the unweighted minimum closure) equals the maximum number of disjoint dijoins that can be found in the graph (a packing of dijoins). A fractional weighted version of the conjecture, posed by

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...

and Rick Giles, was refuted by Alexander Schrijver. In the other direction, the

Lucchesi–Younger theorem In the mathematics of directed graphs, the Lucchesi–Younger theorem is a relationship between dicuts and dijoins. It was published by Cláudio L. Lucchesi and Daniel H. Younger in 1978. Their proof resolved a conjecture that had been posed roughly ...

states that the minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.

References

{{reflist, refs= {{citation , last1 = Abdi , first1 = Ahmad , last2 = Cornuéjols , first2 = Gérard , author2-link = Gérard Cornuéjols , last3 = Zlatin , first3 = Michael , arxiv = 2202.00392 , title = On packing dijoins in digraphs and weighted digraphs , year = 2022 {{citation , last1 = Ahuja , first1 = Ravindra K. , author1-link = Ravindra K. Ahuja , last2 = Magnanti , first2 = Thomas L. , author2-link = Thomas L. Magnanti , last3 = Orlin , first3 = James B. , author3-link = James B. Orlin , contribution = 19.2 Maximum weight closure of a graph , isbn = 0-13-617549-X , location = Englewood Cliffs, NJ , mr = 1205775 , pages = 719–724 , publisher = Prentice Hall Inc. , title = Network flows , year = 1993. {{citation , last1 = Edmonds , first1 = Jack , author1-link = Jack Edmonds , last2 = Giles , first2 = Rick , contribution = A min-max relation for submodular functions on graphs , mr = 0460169 , pages = 185–204 , publisher = North-Holland, Amsterdam , series = Annals of Discrete Mathematics , title = Studies in integer programming (Proc. Workshop, Bonn, 1975) , volume = 1 , year = 1977 {{citation , last = Lovász , first = László , author-link = László Lovász , doi = 10.1016/0095-8956(76)90049-6 , issue = 2 , journal = Journal of Combinatorial Theory , mr = 427138 , pages = 96–103 , series = Series B , title = On two minimax theorems in graph , volume = 21 , year = 1976, doi-access = free {{citation , last1 = Lucchesi , first1 = C. L. , last2 = Younger , first2 = D. H. , doi = 10.1112/jlms/s2-17.3.369 , issue = 3 , journal = Journal of the London Mathematical Society , mr = 500618 , pages = 369–374 , series = Second Series , title = A minimax theorem for directed graphs , volume = 17 , year = 1978 {{citation , last = Noy , first = Marc , doi = 10.2307/2695680 , issue = 1 , journal =

American Mathematical Monthly ''The American Mathematical Monthly'' is a mathematical journal founded by Benjamin Finkel in 1894. It is published ten times each year by Taylor & Francis for the Mathematical Association of America. The ''American Mathematical Monthly'' is an e ...

, mr = 1857074 , pages = 66–68 , title = Acyclic and totally cyclic orientations in planar graphs , volume = 108 , year = 2001, jstor = 2695680 . {{citation , last = Schrijver , first = A. , author-link = Alexander Schrijver , doi = 10.1016/0012-365X(80)90057-6 , issue = 2 , journal =

Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way analogous to discrete variables, having a bijection with the set of natural numbers) rather than "continuous" (analogously to continuous f ...

, mr = 592858 , pages = 213–215 , title = A counterexample to a conjecture of Edmonds and Giles , volume = 32 , year = 1980, doi-access = free {{citation , last = Woodall , first = D. R. , editor1-last = Alavi , editor1-first = Yousef , editor2-last = Lick , editor2-first = Don R. , contribution = Menger and König systems , doi = 10.1007/BFb0070416 , location = Berlin , mr = 499529 , pages = 620–635 , publisher = Springer , series = Lecture Notes in Mathematics , title = Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976) , volume = 642 , year = 1978 Directed graphs