2017/11/18 by Moses Charikar, Charikar, Moses, Shay Solomon +1
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.1711.06883
openalex publication_date 2017/11/18 · openalex created_date 2022/09/14 · openalex updated_date 2026/07/28
Despite significant research efforts, the state-of-the-art algorithm for\nmaintaining an approximate matching in fully dynamic graphs has a polynomial\nworst-case update time, even for very poor approximation guarantees. In a\nrecent breakthrough, Bhattacharya, Henzinger and Nanongkai showed how to\nmaintain a constant approximation to the minimum vertex cover, and thus also a\nconstant-factor estimate of the maximum matching size, with polylogarithmic\nworst-case update time. Later (in SODA'17 Proc.) they improved the\napproximation factor all the way to 2+\ε. Nevertheless, the\nlongstanding fundamental problem of maintaining an approximate matching with\nsub-polynomial worst-case time bounds remained open.\n We present a randomized algorithm for maintaining an almost-maximal\nmatching in fully dynamic graphs with polylogarithmic worst-case update time.\nSuch a matching provides (2+\ε)-approximations for both the maximum\nmatching and the minimum vertex cover, for any \ε > 0. Our result was\ndone independently of the (2+\ε)-approximation result of Bhattacharya\net al., so it provides the first (2+\ε)-approximation for minimum\nvertex cover (together with Bhattacharya et al.'s result) and the first\n(2+\ε)-approximation for maximum (integral) matching.\n The polylogarithmic worst-case update time of our algorithm holds\ndeterministically, while the almost-maximality guarantee holds with high\nprobability. This result not only settles the aforementioned problem on dynamic\nmatchings, but also provides essentially the best possible approximation\nguarantee for dynamic vertex cover (assuming the unique games conjecture).\n