Item

Abstract

We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate
\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges
using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial
improvement over the long-standing $O(n)$ update time, which can be trivially
obtained by periodic recomputation. Thus, we resolve the value version of a
major open question of the dynamic graph algorithms literature (see, e.g.,
[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna
SODA'22]).
Our key technical component is the first sublinear algorithm for $(1,\epsilon
n)$-approximate maximum matching with sublinear running time on dense graphs.
All previous algorithms suffered a multiplicative approximation factor of at
least $1.499$ or assumed that the graph has a very small maximum degree.