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 - Omega(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 epsilon > 0, there is a randomized algorithm that with high probability maintains a 2 - Omega(1) approximate maximum matching of a fully-dynamic general graph in worst-case update time O(Delta(epsilon) + polylog n), where Delta 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(epsilon)) 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].