Simple Deterministic Algorithms for Fully Dynamic Maximal Matching

Abstract

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.