Dynamic Algorithms for Maximum Matching Size

We study fully dynamic algorithms for maximum matching. This is a well-studied problem, known to admit several update-time/approximation trade-offs. For instance, it is known how to maintain a 1/2-approximate matching in (poly log n) update time or a 2/3-approximate matching in O( √ n) update time, where n is the number of vertices. It has been a long-standing open problem to determine whether either of these bounds can be improved.

In this paper, we show that when the goal is to maintain just the size of the matching (and not its edge-set), then these bounds can indeed be improved. First, we give an algorithm that takes (poly log n) update-time and maintains a .501-approximation (.585-approximation if the graph is bipartite). Second, we give an algorithm that maintains a (2/3 + Ω(1))-approximation in O( √ n) time for bipartite graphs.