2026-07-23T20:15:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15690 2024-03-06T10:55:57Z ddc:004 open_access

Deterministic Dynamic Matching in Worst-Case Update Time Kiss, Peter Dynamic Algorithms Matching Approximate Matching EDCS We present deterministic algorithms for maintaining a (3/2 + ε) and (2 + ε)-approximate maximum matching in a fully dynamic graph with worst-case update times Ô(√n) and Õ(1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2 - δ) (for any δ > 0) and (2 + ε) were both shown by Roghani et al. [arXiv'2021] with update times O(n^{3/4}) and O_ε(√n) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are O_ε(√n) and Õ(1) which were shown in Bernstein and Stein [SODA'2021] and Bhattacharya and Kiss [ICALP'2021] respectively. The algorithm achieving (3/2 + ε) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein [ICALP'2015]. Say that H is a (α, δ)-approximate matching sparsifier if at all times H satisfies that μ(H) ⋅ α + δ ⋅ n ≥ μ(G) (define (α, δ)-approximation similarly for matchings). We show how to maintain a locally damaged version of the EDCS which is a (3/2 + ε, δ)-approximate matching sparsifier. We further show how to reduce the maintenance of an α-approximate maximum matching to the maintenance of an (α, δ)-approximate maximum matching building based on an observation of Assadi et al. [EC'2016]. Our reduction requires an update time blow-up of Ô(1) or Õ(1) and is deterministic or randomized against an adaptive adversary respectively. To achieve (2 + ε)-approximation we improve on the update time guarantee of an algorithm of Bhattacharya and Kiss [ICALP'2021]. In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak [STOC'2017] and Bernstein et al. [arXiv'2020] which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. Independent Work: Independently and concurrently to our work Grandoni et al. [arXiv'2021] has presented a fully dynamic algorithm for maintaining a (3/2 + ε)-approximate maximum matching with deterministic worst-case update time O_ε(√n). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Peter Kiss 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.94 urn:nbn:de:0030-drops-156909 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.94 eng https://creativecommons.org/licenses/by/4.0/legalcode