Deterministic Dynamic Matching in Worst-Case Update Time

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. [arXiv\u272021] 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 [SODA\u272021] and Bhattacharya and Kiss [ICALP\u272021] respectively. The algorithm achieving (3/2 + ?) approximation builds on the EDCS concept introduced by the influential paper of Bernstein and Stein [ICALP\u272015]. 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\u272016]. 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 [ICALP\u272021]. In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak [STOC\u272017] and Bernstein et al. [arXiv\u272020] 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\u272021] has presented a fully dynamic algorithm for maintaining a (3/2 + ?)-approximate maximum matching with deterministic worst-case update time O_?(?n)