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 na\"{ \i}ve O(n) one was reported up to this date. The only progress in this direction is due to Ivkovi\'{ c} and Lloyd \cite{ IL93}, who in 1993 devised a deterministic algorithm with an \emph{ amortized} update time of $O((n+m)^{ \sqrt{ 2}/2})$, where $m$ is the number of edges. In this paper we show the first deterministic fully dynamic algorithm that outperforms the trivial one. Specifically, we provide a deterministic \emph{ worst-case} update time of $O(\sqrt{ 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-\eps)$-approximate MCM improving upon the na\"{ \i}ve O(n) was known prior to this work, even allowing amortized time bounds and \emph{ randomization}. For low arboricity graphs (e.g., planar graphs and graphs excluding fixed minors), we devise another simple deterministic algorithm with \emph{ sub-logarithmic update time}. Specifically, it maintains a fully dynamic maximal matching with amortized update time of $O(\log n/\log \log n)$. This result addresses an open question of Onak and Rubinfeld \cite{ OR10}. We also show a deterministic algorithm with optimal space usage, that for arbitrary graphs maintains a maximal matching in amortized $O(\sqrt{ m})$ time, and uses only $O(n+m)$ space.
Categories: cs.DS