Title: Simple Deterministic Algorithms for Fully Dynamic Maximal Matching

Authors: Ofer Neiman and Shay Solomon

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 naive O(n) one was reported up to this date.
The only progress in this direction is due to Ivkovic and
Lloyd, who in 1993 devised a deterministic algorithm
with an 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 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 improvingupon the naive 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 another simple deterministic 
algorithm with sub-logarithmic update time. Specifically, 
it maintains a fully dynamic maximal matching with
amortized update time of O(logn/loglogn).
This result addresses an open question of Onak and Rubinfeld.

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.