Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds

In their breakthrough ICALP’15 paper, Bernstein and Stein presented an algorithm for maintaining a \((3/2+\epsilon)\) -approximate maximum matching in fully dynamic bipartite graphs with a worst-case update time of \(O_{\epsilon}(m^{1/4})\) ; we use the \(O_{\epsilon}\) notation to suppress the \(\epsilon\) -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+\epsilon\) factor. They demonstrate that the EDCS can be maintained with a worst-case update time of \(O_{\epsilon}(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_{\epsilon}(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(\sqrt{m})\) [Neiman and Solomon, STOC’13] and [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 et al., SODA’20]. In this work we ( quasi nanos, gigantium humeris insidentes ) simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it to general graphs while maintaining the same \(O_{\epsilon}(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 \(\alpha\) , then the worst-case update time of the algorithm is \(O_{\epsilon}(\sqrt{\alpha})\) .