Bipartite Graph MCM

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

Space Complexity Graph

Space-Time Tradeoff Improvements

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