Fully Dynamic Matching in Bipartite Graphs

Understand

Maximum cardinality matching in bipartite graphs is an important and well-studied problem.

• The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention.
• Existing algorithms for dynamic matching (in general graphs) seem to fall into two groups: there are fast (mostly randomized) algorithms that do not achieve a better than 2-approximation, and there slow algorithms with $\O(\sqrt{m})$ update time that achieve a better-than-2 approximation.
• Thus the obvious question is whether we can design an algorithm -- deterministic or randomized -- that achieves a tradeoff between these two: a $o(\sqrt{m})$ approximation and a better-than-2 approximation simultaneously.