Fully dynamic maximal independent set with sublinear in N update time

Sepehr Assadi, Krzysztof Onak, Baruch Schieber, Shay Solomon

Research output: Contribution to conferencePaper

9 Scopus citations

Abstract

The first fully dynamic algorithm for maintaining a maximal independent set (MIS) with update time that is sublinear in the number of edges was presented recently by the authors of this paper [Assadi et al. , STOC’18]. The algorithm is deterministic and its update time is O(m3/4), where m is the (dynamically changing) number of edges. Subsequently, Gupta and Khan and independently Du and Zhang [arXiv, April 2018] presented deterministic algorithms for dynamic MIS with update times of O(m2/3) and O(m2/3 log m), respectively. Du and Zhang also gave a randomized algorithm with update time Oe(m). Moreover, they provided some partial (conditional) hardness results hinting that the update time of m1/2−ε, and in particular n1−ε for n-vertex dense graphs, is a natural barrier for this problem for any constant ε > 0, for deterministic and randomized algorithms that satisfy a certain natural property. In this paper, we break this natural barrier and present the first fully dynamic (randomized) algorithm for maintaining an MIS with update time that is always sublinear in the number of vertices, namely, an Oe(n) expected amortized update. We also show that a simpler variant of our algorithm can already achieve an Oe(m1/3) expected amortized update time, which results in an improved performance over our Oe(n) update time algorithm for sufficiently sparse graphs, and breaks the m1/2 barrier of Du and Zhang for all values of m.

Original languageEnglish (US)
Pages1919-1936
Number of pages18
StatePublished - Jan 1 2019
Event30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019 - San Diego, United States
Duration: Jan 6 2019Jan 9 2019

Conference

Conference30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
CountryUnited States
CitySan Diego
Period1/6/191/9/19

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Fully dynamic maximal independent set with sublinear in N update time'. Together they form a unique fingerprint.

  • Cite this

    Assadi, S., Onak, K., Schieber, B., & Solomon, S. (2019). Fully dynamic maximal independent set with sublinear in N update time. 1919-1936. Paper presented at 30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, United States.