Metraipolis › archive › dc_41b026d4c259

Faster Dynamic Maximal Independent Set against Adaptive Adversaries — arXiv:2611.05932

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05932
License (as archived)
CC0-1.0
Archived
2026-11-05T18:31:35.128Z
SHA-256 of the archived text
4135d1f301245b17af290e99a26cd9808a07e5637dc8a6a82d39a4a4a93750dc
Stable URL of this page
https://metraipolis.com/documento/dc_41b026d4c259

How to cite

Faster Dynamic Maximal Independent Set against Adaptive Adversaries — arXiv:2611.05932 — arXiv (en), https://arxiv.org/abs/2611.05932 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_41b026d4c259 (Metraipolis archive dc_41b026d4c259, sha256 4135d1f301245b17af290e99a26cd9808a07e5637dc8a6a82d39a4a4a93750dc)
BibTeX
@misc{dc41b026d4c259,
  title = {Faster Dynamic Maximal Independent Set against Adaptive Adversaries — arXiv:2611.05932},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05932},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_41b026d4c259; sha256 4135d1f301245b17af290e99a26cd9808a07e5637dc8a6a82d39a4a4a93750dc},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05932. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.05932 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-05T18:21:04.025Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).