Simple deterministic algorithms for fully dynamic maximal matching

A maximal matching can be maintained in fully dynamic (supporting both addition and deletion of edges) n-vertex graphs using a trivial deterministic algorithm with a worst-case update time of O(n). No deterministic algorithm that outperforms the näıve O(n) one was reported up to this date. The only progress in this direction is due to Ivkovic ́ and Lloyd [14], who in 1993 devised a deterministic algorithm with an amortized update time of O((n+m) 2/2), where m is the number of edges. In this paper we show the first deterministic fully dynamic algorithm that outperforms the triv-ial one. Specifically, we provide a deterministic worst-case update time of O( m). Moreover, our algorithm maintains a matching which is in fact a 3/2-approximate maximum cardinality matching (MCM). We remark that no fully dynamic algorithm for maintaining (2 − )-approximate MCM im-proving upon the näıve O(n) was known prior to this work, even allowing amortized time bounds and randomization. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise anothe