Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time Bhattacharya, Sayan Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Nanongkai, Danupon We consider the problem of maintaining an approximately maximum (fractional) matching and an approximately minimum vertex cover in a dynamic graph. Starting with the seminal paper by Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. There remains, however, a polynomial gap between the best known worst case update time and the best known amortised update time for this problem, even after allowing for randomisation. Specifically, Bernstein and Stein [ICALP 2015, SODA 2016] have the best known worst case update time. They present a deterministic data structure with approximation ratio (3/2 + ∊) and worst case update time O(m1/4/ ∊2), where m is the number of edges in the graph. In recent past, Gupta and Peng [FOCS 2013] gave a deterministic data structure with approximation ratio (1+ ∊) and worst case update time No known randomised data structure beats the worst case update times of these two results. In contrast, the paper by Onak and Rubinfeld [STOC 2010] gave a randomised data structure with approximation ratio O(1) and amortised update time O(log2 n), where n is the number of nodes in the graph. This was later improved by Baswana, Gupta and Sen [FOCS 2011] and Solomon [FOCS 2016], leading to a randomised date structure with approximation ratio 2 and amortised update time O(1). We bridge the polynomial gap between the worst case and amortised update times for this problem, without using any randomisation. We present a deterministic data structure with approximation ratio (2 + ∊) and worst case update time O(log3 n), for all sufficiently small constants ∊. Society for Industrial and Applied Mathematics 2017 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/11874 Bhattacharya S, Henzinger M, Nanongkai D. Fully dynamic approximate maximum matching and minimum vertex cover in o(log3 n) worst case update time. In: <i>28th Annual ACM-SIAM Symposium on Discrete Algorithms</i>. Vol 0. Society for Industrial and Applied Mathematics; 2017:470-489. doi:<a href="https://doi.org/10.1137/1.9781611974782.30">10.1137/1.9781611974782.30</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1137/1.9781611974782.30 info:eu-repo/semantics/altIdentifier/e-isbn/978-161197478-2 info:eu-repo/semantics/altIdentifier/arxiv/1704.02844 info:eu-repo/semantics/openAccess