Bipartite Graph MCM (Maximum Cardinality Matching)
Jump to navigation
Jump to search
Description
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
Parameters
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)$ auxiliary | Exact | Deterministic | Time |
| Hopcroft–Karp algorithm | 1973 | $O((V^{0.5})$E) | $O(V)$ auxiliary | Exact | Deterministic | Time |
| Mucha; Sankowski (planar) | 2006 | $O(V^{(\omega/{2})$}) where omega is the exponent on matrix multiplication | $O(VlogV)$??? | 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)$ auxiliary?? | Exact | Randomized | Time |
Time Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Space Complexity Graph
Error creating thumbnail: Unable to save thumbnail to destination
Pareto Frontier Improvements Graph
Error creating thumbnail: Unable to save thumbnail to destination
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 | https://arxiv.org/abs/1602.06705 | link |