Fully Dynamic Matching: Beating 2-Approximation in Δϵ Update Time

In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a 2-Ω(1) approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question.

In this paper, we show that for any constant ε > 0, there is a randomized algorithm that with high probability maintains a 2 -Ω(1) approximate maximum matching of a fully-dynamic general graph in worst-case update time O(∆ ε + polylog n), where ∆ is the maximum degree.

Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had O(m 1/4 ) update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time O(n ε ) was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].