Key points are not available for this paper at this time.
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 (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 RS 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. 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^o (1) ORS (n) \ with high probability, even against an adaptive adversary. In the limit, i. e. , if current lower bounds for ORS (n) = n^o (1) are almost optimal, our algorithm achieves an n^o (1) 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.
Assadi et al. (Wed,) studied this question.