Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs

In a very recent breakthrough, Behnezhad and Ghafari [FOCS'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 Ruzsa-Szemerédi Graph-to be the largest number of edge-disjoint matchings M 1 , . . . , M t of size Θ(n) in an n-vertex graph such that for every i ∈ [t], M i is an induced matching in the subgraph M i ∪ M i+1 ∪ . . . ∪ M t .

Then, for any fixed ε > 0, the BG algorithm runs in O n 1+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 Ruzsa-Szemerédi graphs (which require every matching to be induced regardless of the ordering). It is currently only known that n o(1) ⩽ ORS(n) ⩽ n 1-o(1) , and closing this gap appears to be a notoriously challenging problem.

If it turns out that ORS(n) = n o(1) , namely, the current lower bounds are close to being optimal, then, this algorithm achieves an update time of n 1/2+o(1) for (1 -ε)-approximation of fully dynamic matching, making progress on a major open question in the area.