Fully Dynamic Maximal Independent Set with Polylogarithmic Update Time

We present the first algorithm for maintaining a maximal independent set (MIS) of a fully dynamic graph-which undergoes both edge insertions and deletions-in polylogarithmic time. Our algorithm is randomized and, per update, takes O(log 2 Δ log 2 n) expected time. Furthermore, the algorithm can be adjusted to have O(log 2 Δ log 4 n) worst-case update-time with high probability. Here, n denotes the number of vertices and Δ is the maximum degree in the graph. The MIS problem in fully dynamic graphs has attracted significant attention after a breakthrough result of Assadi, Onak, Schieber, and Solomon [STOC'18] who presented an algorithm with O(m 3/4 ) update-time (and thus broke the natural Ω(m) barrier) where m denotes the number of edges in the graph. This result was improved in a series of subsequent papers, though, the update-time remained polynomial. In particular, the fastest algorithm prior to our work had Õ(min{√n, m 1/3 }) update-time [Assadi et al. SODA'19]. Our algorithm maintains the lexicographically first MIS over a random order of the vertices. As a result, the same algorithm also maintains a 3-approximation of correlation clustering. We also show that a simpler variant of our algorithm can be used to maintain a random-order lexicographically first maximal matching in the same update-time.

Authors

• Soheil Behnezhad
• Mahsa Derakhshan
• MohammadTaghi Hajiaghayi
• Cliff Stein 0001
• Madhu Sudan 0001

Keywords

• Heuristic algorithms
• Data structures
• Clustering algorithms
• Correlation
• Standards
• Image edge detection
• Space exploration
• Independent Set
• Maximum Independent Set
• Polylogarithmic
• Maximum Degree
• Lexicographic
• Vertex Degree
• Maximum Matching
• Dynamic Graph
• Data Structure
• Running Time
• Iterative Algorithm
• Proof Of Theorem
• Random Permutations
• Lower Rank
• Rest Of This Section
• Propagation Path
• Probability 1
• Lowest Rank
• Part Of The Proof
• End Of Each Iteration
• Proof Of Claim
• Beginning Of Iteration
• Minimum Rank
• Incident Edges
• Point Of Algorithm
• Fully dynamic
• dynamic
• maximal independent set