@article{11675,
  abstract     = {We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.},
  author       = {Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika H},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic algorithms, Data structures, Graph algorithms, Matching, Vertex cover},
  number       = {4},
  pages        = {1057--1080},
  publisher    = {Springer Nature},
  title        = {{Deterministic dynamic matching in O(1) update time}},
  doi          = {10.1007/s00453-019-00630-4},
  volume       = {82},
  year         = {2020},
}