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 on algorithms that maintain the edges of a $(1-ε)$-approximate maximum matching for an arbitrarily small constant $ε> 0$. Until recently, the fastest known algorithm for this problem required $Θ(n)$ time per update where $n$ is the number of vertices. This bound was slightly improved to $n/(\log^* n)^{Ω(1)}$ by Assadi, Behnezhad, Khanna, and Li [STOC'23] and very recently to $n/2^{Ω(\sqrt{\log n})}$ by Liu [FOCS'24]. Whether this can be improved to $n^{1-Ω(1)}$ remains a major open problem. In this paper, we introduce {\em 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 $δ> 0$, define $ORS(δn)$ to be the maximum number of matchings $M_1, \ldots, M_t$, each of size $δn$, that one can pack in an $n$-vertex graph such that each matching $M_i$ is an {\em induced matching} in subgraph $M_1 \cup \ldots \cup M_{i}$. We show that there is a randomized algorithm that maintains a $(1-ε)$-approximate maximum matching of a fully dynamic graph in $$ \widetilde{O}\left( \sqrt{n^{1+ε} \cdot ORS(Θ_ε(n))} \right) $$ amortized update-time. While the value of $ORS(Θ(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(Θ(n)) \geq n^{1/Θ(\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(ε)}}$, resolving the aforementioned longstanding open problem in dynamic algorithms in a strong sense.