Bipartite Graph MCM (Maximum Cardinality Matching)

From Algorithm Wiki
Revision as of 09:07, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


The goal of maximum cardinality matching is to find a matching with as many edges as possible (equivalently: a matching that covers as many vertices as possible). Here, the graph is bipartite.

Related Problems

Generalizations: General Graph MCM

Subproblem: Planar Bipartite Graph Perfect Matching


$V$: number of vertices

$E$: number of edges

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Micali and Vazirani 1980 $O(V^{0.5} E)$ $O(V)$ Deterministic Time & Space
Ford–Fulkerson algorithm 1956 $O(VE)$ $O(E)$ Exact Deterministic Time
Hopcroft–Karp algorithm 1973 $O((V^{0.5})$E) $O(V)$ Exact Deterministic Time
Mucha; Sankowski (planar) 2006 $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication $O(V \log V)$??? Exact Randomized Time
Madry's algorithm 2013 $O(E^{10/7}*polylog(V)$) $O(E + V)$ Exact Deterministic Time
Chandran and Hochbaum 2011 $O(min(V*k, E)$+sqrt(k)*min(k^{2}, E)) $O(E)$?? Exact Randomized Time

Time Complexity Graph

Maximum Cardinality Matching - Bipartite Graph MCM - Time.png

Reductions FROM Problem

Problem Implication Year Citation Reduction
OuMv assume: OMv
then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$
2016 link