---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Sayan
foaf_name: Bhattacharya, Sayan
foaf_surname: Bhattacharya
- foaf_Person:
foaf_givenName: Deeparnab
foaf_name: Chakrabarty, Deeparnab
foaf_surname: Chakrabarty
- foaf_Person:
foaf_givenName: Monika H
foaf_name: Henzinger, Monika H
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
orcid: 0000-0002-5008-6530
bibo_doi: 10.1007/s00453-019-00630-4
bibo_issue: '4'
bibo_volume: 82
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0178-4617
- http://id.crossref.org/issn/1432-0541
dct_language: eng
dct_publisher: Springer Nature@
dct_subject:
- Dynamic algorithms
- Data structures
- Graph algorithms
- Matching
- Vertex cover
dct_title: Deterministic dynamic matching in O(1) update time@
...