---
_id: '11675'
abstract:
- lang: eng
  text: '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.'
article_processing_charge: No
article_type: original
author:
- first_name: Sayan
  full_name: Bhattacharya, Sayan
  last_name: Bhattacharya
- first_name: Deeparnab
  full_name: Chakrabarty, Deeparnab
  last_name: Chakrabarty
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic dynamic matching
    in O(1) update time. <i>Algorithmica</i>. 2020;82(4):1057-1080. doi:<a href="https://doi.org/10.1007/s00453-019-00630-4">10.1007/s00453-019-00630-4</a>
  apa: Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. H. (2020). Deterministic
    dynamic matching in O(1) update time. <i>Algorithmica</i>. Springer Nature. <a
    href="https://doi.org/10.1007/s00453-019-00630-4">https://doi.org/10.1007/s00453-019-00630-4</a>
  chicago: Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic
    Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>. Springer Nature, 2020.
    <a href="https://doi.org/10.1007/s00453-019-00630-4">https://doi.org/10.1007/s00453-019-00630-4</a>.
  ieee: S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic dynamic
    matching in O(1) update time,” <i>Algorithmica</i>, vol. 82, no. 4. Springer Nature,
    pp. 1057–1080, 2020.
  ista: Bhattacharya S, Chakrabarty D, Henzinger MH. 2020. Deterministic dynamic matching
    in O(1) update time. Algorithmica. 82(4), 1057–1080.
  mla: Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update
    Time.” <i>Algorithmica</i>, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80,
    doi:<a href="https://doi.org/10.1007/s00453-019-00630-4">10.1007/s00453-019-00630-4</a>.
  short: S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, Algorithmica 82 (2020) 1057–1080.
date_created: 2022-07-27T14:31:06Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2022-09-12T08:55:46Z
day: '01'
doi: 10.1007/s00453-019-00630-4
extern: '1'
intvolume: '        82'
issue: '4'
keyword:
- Dynamic algorithms
- Data structures
- Graph algorithms
- Matching
- Vertex cover
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1007/s00453-019-00630-4
month: '04'
oa: 1
oa_version: Published Version
page: 1057-1080
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic dynamic matching in O(1) update time
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 82
year: '2020'
...