Fully dynamic maximal independent set with sublinear update time

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{Δ, m 3/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{Δ, m 3/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.

Authors

• Sepehr Assadi
• Krzysztof Onak
• Baruch Schieber
• Shay Solomon

Keywords

• dynamic distributed algorithms
• dynamic graph algorithms
• maximal independent set