cs.DS
Fully Dynamic Maximal Independent Set in Expected Poly Log Update Time. In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph G while edges are inserted and deleted from the graph. The first non trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon STOC 2018 who obtained a deterministic fully dynamic MIS with O(m 3 4 ) update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan arXiv 2018 to tilde O (m 2 3 ) update time. Du and Zhang arXiv 2018 also presented a randomized algorithm against an oblivious adversary with tilde O ( sqrt m ) update time. The current state of art is by Assadi, Onak, Schieber, and Solomon SODA 2019 who obtained randomized algorithms against oblivious adversary with tilde O ( sqrt n ) and tilde O (m 1 3 ) update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst case update time of O( log 4n) . As a direct corollary, one can apply the black box reduction from a recent work by Bernstein, Forster, and Henzinger SODA 2019 to achieve O( log 6n) worst case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly log.