Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs

We study the fully dynamic maximum matching problem. In this problem, the goal is to efficiently maintain an approximate maximum matching of a graph that is subject to edge insertions and deletions. Our focus is particularly on algorithms that maintain the edges of a$(1-\varepsilon)$-approximate maximum matching for an arbitrarily small constant$\varepsilon > 0$. Until recently, the fastest known algorithm for this problem required$\Theta(n)$time per update where$n$is the number of vertices. This bound was slightly improved to$n/(\log^{\ast}n)^{\Omega(1)}$by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to$n/2_{-}^{\Omega(\sqrt{\log n})}$by Liu [FOCS'24]. Whether this can be improved to$n^{1-\Omega(1)}$remains a major open problem. In this paper, we introduce Ordered Ruzsa-Szemerédi (ORS) graphs (a generalization of Ruzsa-Szemerédi graphs) and show that the complexity of dynamic matching is closely tied to them. For$\delta > 0$, define ORS$(\delta n)$to be the maximum number of matchings$M_{1}, \ldots, 1M_{t}$, each of size$\delta n$, that one can pack in an n-vertex graph such that each matching$M_{i}$is an induced matching in subgraph$M_{1}\cup\ldots\cup M_{i}$. We show that there is a randomized algorithm that maintains a$(1-\varepsilon)$-approximate maximum matching of a fully dynamic graph in amortized update-time. While the value of$\text{ORS}(\Theta(n))$remains unknown and is only upper bounded by$n^{1-o(1)}$, the densest construction known from more than two decades ago only achieves$ORS (\Theta(n))\geq n^{1/\Theta(\log\log n)}=n^{o(1)}$[Fischer et al. STOC'02]. If this is close to the right bound, then our algorithm achieves an update-time of$\sqrt{n^{1+O(\varepsilon)}}^{-}$, resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.