# 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.