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, 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).[1][2] A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver.[3][4][1]
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.[5][6] The minimum weight dijoin in a weighted graph can be found in polynomial time,[7] and is a special case of the submodular flow problem.[8]
In planar graphs, dijoins and feedback arc sets 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. 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.[9] 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 for other types of graphs.[7]
References
- ^ a b Abdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv:2202.00392
- ^ 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
- ^ 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), "A counterexample to a conjecture of Edmonds and Giles", 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
- ^ a b Frank, András (1981), "How to make a digraph strongly connected", Combinatorica, 1 (2): 145–153, doi:10.1007/BF02579270, MR 0625547, S2CID 27825518
- ^ Gabow, Harold N. (1993), "A framework for cost-scaling algorithms for submodular flow problems", Proceedings of the 34th Annual Symposium on Foundations of Computer Science (FOCS), Palo Alto, California, USA, 3-5 November 1993, IEEE Computer Society, pp. 449–458, doi:10.1109/SFCS.1993.366842
- ^ Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022, MR 1334365