Dynamic Distributed MIS with Improved Bounds
share
The problem of maintaining a maximal independent set (MIS) in a dynamic graph has received growing attention in recent years. In STOC'18, Assadi et al. presented a distributed algorithm for maintaining an MIS with O(1) (amortized) round complexity and O(m^3/4) message complexity, where m denotes the dynamic number of edges in the graph. The algorithm of Assadi et al. is deterministic; to the best of our knowledge, the state-of-the-art distributed algorithm for this problem with a message complexity of o(m^3/4) incurs a round complexity of Ω(m^1/3). We propose a deterministic distributed algorithm that achieves an amortized message complexity of Õ(m^2/3) and an amortized round complexity of Õ(1) under fully dynamic edge updates in the CONGEST model, where Õ(·) suppresses polylogarithmic factors.
READ FULL TEXT