Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemer\'edi Graphs

In a very recent breakthrough, Behnezhad and Ghafari [arXiv'24] developed a novel fully dynamic randomized algorithm for maintaining a (1-ε)-approximation of maximum matching with amortized update time potentially much better than the trivial $O(n)$ update time. The runtime of the BG algorithm is parameterized via the following graph theoretical concept: * For any n, define $ORS(n)$ -- standing for Ordered RS Graph -- to be the largest number of edge-disjoint matchings M₁,…,Mₜ of size Θ(n) in an n-vertex graph such that for every i ∈ [t], Mᵢ is an induced matching in the subgraph Mᵢ ∪ Mᵢ₊₁ ∪ … ∪ Mₜ. Then, for any fixed ε > 0, the BG algorithm runs in \[ O( √{n1+O(ε) · ORS(n)} ) \] amortized update time with high probability, even against an adaptive adversary. $ORS(n)$ is a close variant of a more well-known quantity regarding RS graphs (which require every matching to be induced regardless of the ordering). It is currently only known that nᵒ⁽¹⁾ ORS(n) n¹⁻ᵒ⁽¹⁾, and closing this gap appears to be a notoriously challenging problem. In this work, we further strengthen the result of Behnezhad and Ghafari and push it to limit to obtain a randomized algorithm with amortized update time of \[ nᵒ⁽¹⁾ · ORS(n) \] with high probability, even against an adaptive adversary. In the limit, i.e., if current lower bounds for ORS(n) = nᵒ⁽¹⁾ are almost optimal, our algorithm achieves an nᵒ⁽¹⁾ update time for (1-ε)-approximation of maximum matching, almost fully resolving this fundamental question. In its current stage also, this fully reduces the algorithmic problem of designing dynamic matching algorithms to a purely combinatorial problem of upper bounding $ORS(n)$ with no algorithmic considerations.