Lucchesi-Younger theorem
From Egres Open
Theorem (Lucchesi, Younger[1]). In a directed graph, the minimum size of a dijoin equals the maximum number of pairwise edge-disjoint directed cuts.
The following weighted version is equivalent:
Theorem. Let D=(V,A) be a digraph, and let [math]w:A \to {\mathbb Z}_+[/math] be a weight function on the arcs. The minimum weight of a dijoin equals the maximum number of directed cuts that contain each arc a only w(a) times.
This theorem can be seen as a special case of the Edmonds-Giles theorem. In fact, it was shown by Frank and Tardos [2] that finding the minimum weight k-dijoin can be reduced to weighted matroid intersection. Currently the fastest algorithm for finding minimum size dijoins is by Gabow [3].
References
- ↑ C. Lucchesi, D. Younger, A minimax theorem for directed graphs, J. London Math. Soc. (2) 17 (1978), 369--374. PDF
- ↑ A. Frank, É. Tardos, Matroids from crossing families, Proceedings Sixth Hungarian Combinatorial Colloquium (1981), North Holland (1984) 295-304. Author link.
- ↑ H.N. Gabow, Centroids, representations, and submodular flows, Journal of Algorithms 18 (1995), 586–628. DOI link.
