Fully Dynamic Maximal Independent Set with Sublinear Update Time

Authors: Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon.
Conference: 50th Annual ACM Symposium on the Theory of Computing (STOC'18)
Abstract: 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(min{∆,m3/4}), where ∆ 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(min{∆,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.