Abstract
We follow the recent breakthrough of Behnezhad and Ghafari [FOCS'24] in designing fully dynamic algorithms for the maximum matching problem whose runtimes is parameterized by the density of the so-called Ordered Ruzsa-Szemeredi (ORS) Graphs. These are graphs whose edges can be partitioned into an ordered set of linear-size matchings such that each matching is induced among the edges of the matchings that appear after it in this ordering. Behnezhad and Ghafari developed an algorithm for (1+eps)-approximation of matchings for any constant eps with update time roughly \sqrt{n * ORS(n)}, where ORS(n) denotes the largest number of matchings possible in an n-vertex ORS graph. The parameter ORS(n) is still quite poorly understood and we effectively only know that it is between n^{o(1)} and o(n). Under the plausible scenario that the current lower bounds for ORS(n) are almost optimal, the BG algorithm will run in n^{1/2+o(1)} update time, which will be a major achievement in this area.
In this talk, we will cover our recent improvements to the BG-algorithm that improve the update time to only n^{o(1)} * ORS(n). This means that under the plausible scenario above, this algorithm simply runs in n^{o(1)} update time. 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.