Maximum cardinality matching
Maximum cardinality matching is a fundamental problem in graph theory.
1. The Ford–Fulkerson algorithm finds a maximum-cardinality matching by repeatedly finding an augmenting path from some x ∈ X to some y ∈ Y and updating the matching M by taking the symmetric difference of that path with M (assuming such a path exists). As each path can be found in time, the running time is . This solution is equivalent to adding a super source with edges to all vertices in , and a super sink with edges from all vertices in , and finding a maximal flow from to . All edges with flow from to then constitute a maximum matching.
3. An alternative randomized approach is based on the fast matrix multiplication algorithm and gives complexity, which is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.
4. For sparse graphs, is possible with Madry's algorithm based on electric flows.
5. The algorithm of Chandran and Hochbaum runs in time that depends on the size of the maximum matching , which for is .
6. Using boolean operations on words of size the complexity is further improved to .
Applications and generalizationsEdit
- West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2
- Micali, S.; Vazirani, V. V. (1980), "An algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, doi:10.1109/SFCS.1980.12.
- Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF), Proc. 45th IEEE Symp. Foundations of Computer Science, pp. 248–255
- Chandran, Bala G.; Hochbaum, Dorit S. (2011), Practical and theoretical improvements for bipartite matching using the pseudoflow algorithm, arXiv:1105.1569, Bibcode:2011arXiv1105.1569C,
the theoretically efficient algorithms listed above tend to perform poorly in practice.
- Madry, A (2013), "Navigating Central Path with Electrical Flows: From Flows to Matchings, and Back", Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp. 253–262, arXiv:1307.2205, Bibcode:2013arXiv1307.2205M
- Borradaile, Glencora; Klein, Philip N.; Mozes, Shay; Nussbaum, Yahav; Wulff–Nilsen, Christian (2017), "Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time", SIAM Journal on Computing, 46 (4): 1280–1303, arXiv:1105.2228, doi:10.1137/15M1042929, MR 3681377