Faster updates for dynamic graph maximal independent sets against adaptive changes

Faster Dynamic Maximal Independent Set against Adaptive Adversaries

Data Structures and Algorithms

Summary

Maintaining a special selection of points in a changing network, where no two chosen points connect directly, is important but can be slow when the network changes unpredictably. Previous fast methods only worked if the changes were fixed ahead of time, and slower methods existed for more adaptive situations. The authors created a new method that speeds up updating this selection even when changes depend on previous outcomes. Their approach is the first to improve the speed significantly over older methods in this adaptive setting.

What this means in practice

  • For network engineers: Improve real-time network management by faster maintenance of maximal independent sets as network links frequently change in response to traffic or failures.
  • For distributed systems developers: Enhance distributed resource allocation algorithms by using quicker updates for conflict-free sets when system connections adapt based on prior state.

Authors

Hongyi Chen, Shuyan Fan, Tianyi Zhang

Abstract

We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions and deletions. Against an oblivious adversary, which fixes the edge update sequence in advance, the randomized algorithms of Behnezhad et al. (2019) and Chechik and Zhang (2019) achieve polylogarithmic update time. Against an adaptive adversary, which may choose each update after observing the previously reported MISs, the best previously known update bound was $O(m^{2/3})$, given by the deterministic algorithm of Gupta and Khan (2018, 2021). Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein et al. (2026) proved that any combinatorial algorithm against an adaptive adversary requires at least $m^{1/2-o(1)}$ update time even under edge insertions alone, leaving a polynomial gap between upper and lower bounds. We present a randomized fully dynamic MIS algorithm with $\widetilde O(m^{5/8})=\widetilde O(m^{2/3-1/24})$ update time against adaptive adversaries. This gives the first polynomial improvement over the $m^{2/3}$ bound for adaptive fully dynamic MIS.