In mathematics, a dijoin is a subset of the edges of a

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

, 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, includes at least one edge crossing the dicut. Here, a dicut is a partition of the vertices into two subsets, so that each edge that has an endpoint in both subsets is directed from the first subset to the second. Woodall's conjecture, 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 Alexander (Lex) Schrijver (born 4 May 1948 in Amsterdam) is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in ...

. The Lucchesi–Younger theorem states that the minimum size of a dijoin, in any given directed graph, equals the maximum number of disjoint dicuts that can be found in the graph. The minimum weight dijoin in a weighted graph can be found 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 ...

, and is a special case of the

submodular flow In the theory of combinatorial optimization, submodular flow is a general class of optimization problems that includes as special cases the minimum-cost flow problem, matroid intersection, and the problem of computing a minimum-weight dijoin in a ...

problem. 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, dijoins and

feedback arc set In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks al ...

s are dual concepts. The

dual graph In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...

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. A feedback arc set is a subset of the edges that includes at least one edge from every directed cycle. For a dijoin in the given graph, the corresponding set of edges forms a directed cut in the dual graph, and vice versa. This relationship between these two problems allows the feedback arc set problem to be solved efficiently for planar graphs, even though it is

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

for other types of graphs.

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 = 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 = Frank , first = András , author-link = András Frank , doi = 10.1007/BF02579270 , issue = 2 , journal =

Combinatorica ''Combinatorica'' is an international journal of mathematics, publishing papers in the fields of combinatorics and computer science. It started in 1981, with László Babai and László Lovász as the editors-in-chief with Paul Erdős as honora ...

, mr = 625547 , pages = 145–153 , title = How to make a digraph strongly connected , volume = 1 , year = 1981, s2cid = 27825518 {{citation , last = Gabow , first = Harold N. , author-link = Harold N. Gabow , contribution = A framework for cost-scaling algorithms for submodular flow problems , doi = 10.1109/SFCS.1993.366842 , pages = 449–458 , publisher = IEEE Computer Society , title = Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, USA, 3-5 November 1993 , year = 1993 {{citation , last = Gabow , first = Harold N. , author-link = Harold N. Gabow , doi = 10.1006/jagm.1995.1022 , issue = 3 , journal = Journal of Algorithms , mr = 1334365 , pages = 586–628 , title = Centroids, representations, and submodular flows , volume = 18 , year = 1995 {{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 = 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