# Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

arXiv: https://arxiv.org/abs/1909.03478 · HTML: https://mlsanity.com/paper/1909.03478/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2019.

## Built on by (most cited first, 5 of 5)

- [Dynamic Correlation Clustering in Sublinear Update Time](https://mlsanity.com/paper/2406.09137/) (2024)
- [Dynamic algorithms for k-center on graphs](https://mlsanity.com/paper/2307.15557/) (2023)
- [Fully Dynamic Adversarially Robust Correlation Clustering in Polylogarithmic Update Time](https://mlsanity.com/paper/2411.09979/) (2024)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [Inductive Correlation Clustering with Graph Neural Networks](https://mlsanity.com/paper/2608.27153/) (2026)

## Abstract (arXiv)

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph---which undergoes both edge insertions and deletions---in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log2 Delta · log2 n) expected time. Furthermore, the algorithm can be adjusted to have O(log2 Delta · log4 n) worst-case update-time with high probability. Here, n denotes the number of vertices and Delta is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m3/4) update-time (and thus broke the natural Omega(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had widetildeO(min√n, m1/3) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.