# Fully Dynamic Maximal Independent Set with Sublinear Update Time

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Feb 2018.

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

- [Learning for Dynamic Combinatorial Optimization without Training Data](https://mlsanity.com/paper/2505.19497/) (2025)

## Abstract (arXiv)

A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(minDelta,m3/4), where Delta is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O(minDelta,m3/4) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC'16) that required an assumption of a non-adaptive oblivious adversary.