Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Authors:
- 1 November 2019
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 370-381
Abstract
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 Õ(m^2/3) update time^1 Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with Õ(√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 Õ(√n) and Õ(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.Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching2019
- Fully dynamic maximal independent set with sublinear update time2018
- Optimal Dynamic Distributed MIS2016
- Distributed -coloring in the physical modelTheoretical Computer Science, 2014
- Leader election in shared spectrum radio networks2012
- Distributive graph algorithms Global solutions from local data1987
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- A Simple Parallel Algorithm for the Maximal Independent Set ProblemSIAM Journal on Computing, 1986