2016/11/01 by Sayan Bhattacharya, Bhattacharya, Sayan, Deeparnab Chakrabarty +3 · 2 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1611.00198
openalex publication_date 2016/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problems of maintaining an approximate maximum matching and\nan approximate minimum vertex cover in a dynamic graph undergoing a sequence of\nedge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld\n[STOC 2010], this problem has received significant attention in recent years.\nVery recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011],\nSolomon [FOCS 2016] gave a randomized dynamic algorithm for this problem that\nhas an approximation ratio of 2 and an amortised update time of O(1) with\nhigh probability. This algorithm requires the assumption of an em oblivious\nadversary, meaning that the future sequence of edge insertions/deletions in\nthe graph cannot depend in any way on the algorithm's past output. A natural\nway to remove the assumption on oblivious adversary is to give a deterministic\ndynamic algorithm for the same problem in O(1) update time. In this paper, we\nresolve this question.\n We present a new em deterministic fully dynamic algorithm that maintains a\nO(1)-approximate minimum vertex cover and maximum fractional matching, with\nan amortised update time of O(1). Previously, the best deterministic\nalgorithm for this problem was due to Bhattacharya, Henzinger and Italiano\n[SODA 2015]; it had an approximation ratio of (2+\ε) and an amortised\nupdate time of O(\log n/\ε2). Our results also extend to a fully\ndynamic O(f3)-approximate algorithm with O(f2) amortized update time for\nthe hypergraph vertex cover and fractional hypergraph matching problems, where\nevery hyperedge has at most f vertices.\n