In their breakthrough ICALP’15 paper, Bernstein and Stein presented an algorithm for maintaining a \ ( (3/2+) \) -approximate maximum matching in fully dynamic bipartite graphs with a worst-case update time of \ (O_ (m^1/4) \) ; we use the \ (O_\) notation to suppress the \ (\) -dependence. Their main technical contribution was in presenting a new type of bounded-degree subgraph, which they named an edge degree constrained subgraph (EDCS), which contains a large matching — of size that is smaller than the maximum matching size of the entire graph by at most a \ (3/2+\) factor. They demonstrate that the EDCS can be maintained with a worst-case update time of \ (O_ (m^1/4) \), and their main result follows as a direct corollary. In their followup SODA’16 paper, Bernstein and Stein generalized their result for general graphs, achieving the same update time of \ (O_ (m^1/4) \), albeit with an amortized rather than worst-case bound. To date, the best deterministic worst-case update time bound for any better-than-2 approximate matching is \ (O (m) \) Neiman and Solomon, STOC’13, Gupta and Peng, FOCS’13; allowing randomization (against an oblivious adversary) one can achieve a much better (still polynomial) update time for approximation slightly below 2 Behnezhad, Łacki and Mirrokni, SODA’20. In this work we 1 simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it to general graphs while maintaining the same \ (O_ (m^1/4) \) bound on the worst-case update time. Moreover, our approach is density-sensitive: If the arboricity of the dynamic graph is always bounded by \ (\), then the worst-case update time of the algorithm is \ (O_ () \).
Grandoni et al. (Mon,) studied this question.