Search

We present deterministic algorithms for maintaining a (3 / 2 + ϵ) and (2 + ϵ) -approximate maximum matching in a fully dynamic graph with worst-case update times O ^ (n) and O ~ (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. (Beating the folklore algorithm for dynamic matching, 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 O ~ (1) which were shown in Bernstein and Stein (in: Proceedings of the twenty-seventh annual ACM-SIAM symposium on discrete algorithms, 2016) and Bhattacharya and Kiss (in: 48th international colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021) respectively. The algorithm achieving (3 / 2 + ϵ) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein (in: International colloquium on automata, languages, and programming, Springer, Berlin, 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. (in: Proceedings of the twenty-seventh annual (ACM-SIAM) symposium on discrete algorithms, (SODA) 2016, Arlington, VA, USA, January 10–12, 2016). Our reduction requires an update time blow-up of O ^ (1) or O ~ (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 (in: 48th International colloquium on automata, languages, and programming, ICALP 2021, 12–16 July, Glasgow, 2021). In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak (in: Proceedings of the twenty-seventh annual ACM symposium on theory of computing, 2017) and Bernstein et al. (Fully-dynamic graph sparsifiers against an adaptive adversary, 2020) which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time. [ABSTRACT FROM AUTHOR]