Dynamic maximal independent set updates improved using prediction errors
Dynamic Maximal Independent Set using Predictions
Data Structures and Algorithms
Summary
Maintaining a maximal independent set (MIS) in a changing network is usually slow when edges are added or removed. The authors develop algorithms that speed up these updates by using predictions about what changes will happen, but they only run fast if the predictions are mostly correct. The faster update times depend on how many updates or nodes were mispredicted, so the methods gradually slow down as prediction errors increase. Their approach works for adding edges, removing edges, or both, and stores data efficiently to handle large graphs.
What this means in practice
- •For network operators: Maintain up-to-date independent sets in evolving communication or social networks faster by using predicted changes to optimize update times.
- •For database administrators: Improve the efficiency of handling dynamic graph data in databases where edges are frequently inserted or deleted, by leveraging predicted update patterns.
Authors
Shahbaz Khan, Anshul Kumar
Abstract
We present the first dynamic maximal independent set (MIS) of a graph with $n$ vertices and up to $m$ edges under edge updates in the prediction model, where a predicted update sequence is available for offline preprocessing before the real updates arrive online. We consider the incremental (insertion-only), decremental (deletions-only), and fully dynamic (insertions and deletions) models. Without predictions, deterministic algorithms need worst-case update time of $O(n)$ for decremental and $O(m)$ for incremental and fully dynamic settings. Bernstein et al.~[SODA26] proved under the combinatorial BMM conjecture, combinatorial incremental algorithms against an adaptive adversary require $Ω(n^{1-o(1)})$ amortized update time. We present deterministic incremental, decremental, and fully dynamic algorithms whose update times depend on the prediction error. This error is measured by the number $η_e$ of mispredicted updates, and by the number $η_v$ and total degree $η_v^*$ of vertices whose MIS membership was mispredicted. With $O(mn)$ preprocessing, our decremental and incremental algorithms achieve worst-case update times $O(η_v)$ and $O(η_e+η_v^*)$, respectively. Our fully dynamic algorithm achieves $O(η_e+η_v^*)$ worst-case update time with $O(un)$ preprocessing for $u$ updates. We also give space-efficient variants using $O(m)$ space for the decremental and $O(m\sqrt{m})$ for the incremental setting, at the cost of a logarithmic overhead in worst-case update time. Our algorithms satisfy consistency, robustness, and smooth degradation, the required properties of algorithms with predictions. They can also utilize the general error correction framework of Khan et al.~[Arxiv26], relaxing the error measures from first point of difference to prefix matching (for partially dynamic) and set edit distance (for fully dynamic), maintaining the same bounds.