Maximum cardinality matching

  (Redirected from Maximum matching)

Maximum cardinality matching is a fundamental problem in graph theory.

Given a bipartite graph , the goal is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible).[1]

AlgorithmsEdit

1. The Ford–Fulkerson algorithm finds a maximum-cardinality matching by repeatedly finding an augmenting path from some xX to some yY 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.

2. An improvement over this is the Hopcroft–Karp algorithm, which runs in   time. Micali and Vazirani's matching algorithm also runs in time O(VE) time.[2]

3. An alternative randomized approach is based on the fast matrix multiplication algorithm and gives   complexity,[3] which is better in theory for sufficiently dense graphs, but in practice the algorithm is slower.[4]

4. For sparse graphs,   is possible with Madry's algorithm based on electric flows.[5]

5. The algorithm of Chandran and Hochbaum[4] 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  .[citation needed]

7. By reducing the problem to maximum flow with multiple sources and sinks, the maximum matching problem in  -vertex bipartite planar graphs can be solved in time  .[6]

Applications and generalizationsEdit

  • By finding a maximum-cardinality matching, it is possible to decide whether there exists a perfect matching.
  • The blossom algorithm finds a maximum-cardinality matching in general (not bipartite) graphs.
  • The assignment problem finds a maximum-weight matching in a bipartite weighted graph.

ReferencesEdit

  1. ^ West, Douglas Brent (1999), Introduction to Graph Theory (2nd ed.), Prentice Hall, Chapter 3, ISBN 0-13-014400-2
  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.
  3. ^ Mucha, M.; Sankowski, P. (2004), "Maximum Matchings via Gaussian Elimination" (PDF), Proc. 45th IEEE Symp. Foundations of Computer Science, pp. 248–255
  4. ^ a b 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.
  5. ^ 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
  6. ^ 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