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.[1][2] Their proof resolved a conjecture that had been posed roughly a decade earlier by Younger,[3] and in unpublished work by Neil Robertson,[2] motivated by the duality in planar graphs between dijoins and feedback arc sets.[2][4]
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.[5]
If a collection of dicuts are all disjoint, any dijoin must have at least one edge from each of these dicuts, and must have size at least equal to the size of the collection. Therefore, the maximum number of disjoint dicuts in any graph must be less than or equal to the minimum size of a dijoin. The Lucchesi–Younger theorem states that this relation is always an equality. The minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.[1][2]
References
edit- ^ a b 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
- ^ a b c d 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
- ^ Younger, D. H. (1969), "Maximum families of disjoint directed cut sets", Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), Academic Press, pp. 329–333, MR 0258678
- ^ Gabow, Harold N. (1995), "Centroids, representations, and submodular flows", Journal of Algorithms, 18 (3): 586–628, doi:10.1006/jagm.1995.1022, MR 1334365
- ^ Abdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv:2202.00392