Fully dynamic maximal independent set with sublinear update time

Sepehr Assadi, Baruch Schieber, Krzysztof Onak, Shay Solomon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

14 Scopus citations

Abstract

A maximal independent set (MIS) can be maintained in an evolving m-edge graph by simply recomputing it from scratch in O(m) time after each update. But can it be maintained in time sublinear in m in fully dynamic graphs? We answer this fundamental open question in the affirmative. We present a deterministic algorithm with amortized update time O(min{∆,m3/4}), where ∆ is a fixed bound on the maximum degree in the graph and m is the (dynamically changing) number of edges. We further present a distributed implementation of our algorithm with O(min{∆,m3/4}) amortized message complexity, and O(1) amortized round complexity and adjustment complexity (the number of vertices that change their output after each update). This strengthens a similar result by Censor-Hillel, Haramaty, and Karnin (PODC’16) that required an assumption of a non-adaptive oblivious adversary.

Original languageEnglish (US)
Title of host publicationSTOC 2018 - Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
EditorsMonika Henzinger, David Kempe, Ilias Diakonikolas
PublisherAssociation for Computing Machinery
Pages431-444
Number of pages14
ISBN (Electronic)9781450355599
DOIs
StatePublished - Jun 20 2018
Externally publishedYes
Event50th Annual ACM Symposium on Theory of Computing, STOC 2018 - Los Angeles, United States
Duration: Jun 25 2018Jun 29 2018

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference50th Annual ACM Symposium on Theory of Computing, STOC 2018
CountryUnited States
CityLos Angeles
Period6/25/186/29/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamic distributed algorithms
  • Dynamic graph algorithms
  • Maximal independent set

Cite this