Fully dynamic MIS in uniformly sparse graphs

Krzysztof Onak, Baruch Schieber, Shay Solomon, Nicole Wein

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

8 Scopus citations

Abstract

We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (STOC 2018) showed that an MIS can be maintained in sublinear (in the dynamically changing number of edges) amortized update time. In this paper we significantly improve the update time for uniformly sparse graphs. Specifically, for graphs with arboricity α, the amortized update time of our algorithm is O(α2 · log2 n), where n is the number of vertices. For low arboricity graphs, which include, for example, minor-free graphs as well as some classes of “real world” graphs, our update time is polylogarithmic. Our update time improves the result of Assadi et al. for all graphs with arboricity bounded by m3/8−, for any constant > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m1/2.

Original languageEnglish (US)
Title of host publication45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
EditorsChristos Kaklamanis, Daniel Marx, Ioannis Chatzigiannakis, Donald Sannella
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770767
DOIs
StatePublished - Jul 1 2018
Externally publishedYes
Event45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 - Prague, Czech Republic
Duration: Jul 9 2018Jul 13 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume107
ISSN (Print)1868-8969

Other

Other45th International Colloquium on Automata, Languages, and Programming, ICALP 2018
Country/TerritoryCzech Republic
CityPrague
Period7/9/187/13/18

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamic graph algorithms
  • Graph arboricity
  • Independent set
  • Sparse graphs

Cite this