Fully Dynamic Maximal Matching in Constant Update Time

Understand

Baswana, Gupta and Sen [FOCS'11] showed that fully dynamic maximal matching can be maintained in general graphs with logarithmic amortized update time.

• More specifically, starting from an empty graph on $n$ fixed vertices, they devised a randomized algorithm for maintaining maximal matching over any sequence of $t$ edge insertions and deletions with a total runtime of $O(t \log n)$ in expectation and $O(t \log n + n \log^2 n)$ with high probability.
• Whether or not this runtime bound can be improved towards $O(t)$ has remained an important open problem.
• Despite significant research efforts, this question has resisted numerous attempts at resolution even for basic graph families such as forests.