2019/11/05 by Soheil Behnezhad, Behnezhad, Soheil, Jakub Łącki +3
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Privacy-Preserving Technologies in Data #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.1911.01839
openalex publication_date 2019/11/05 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
In fully dynamic graphs, we know how to maintain a 2-approximation of maximum matching extremely fast, that is, in polylogarithmic update time or better. In a sharp contrast and despite extensive studies, all known algorithms that maintain a 2-Ω(1) approximate matching are much slower. Understanding this gap and, in particular, determining the best possible update time for algorithms providing a better-than-2 approximate matching is a major open question. In this paper, we show that for any constant ε> 0, there is a randomized algorithm that with high probability maintains a 2-Ω(1) approximate maximum matching of a fully-dynamic general graph in worst-case update time O(Δε+polylog n), where Δ is the maximum degree. Previously, the fastest fully dynamic matching algorithm providing a better-than-2 approximation had O(m1/4) update-time [Bernstein and Stein, SODA 2016]. A faster algorithm with update-time O(nε) was known, but worked only for maintaining the size (and not the edges) of the matching in bipartite graphs [Bhattacharya, Henzinger, and Nanongkai, STOC 2016].