License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.92
URN: urn:nbn:de:0030-drops-90968
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9096/
Go to the corresponding LIPIcs Volume Portal

Onak, Krzysztof ; Schieber, Baruch ; Solomon, Shay ; Wein, Nicole

Fully Dynamic MIS in Uniformly Sparse Graphs

pdf-format:
LIPIcs-ICALP-2018-92.pdf (0.4 MB)

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 alpha, the amortized update time of our algorithm is O(alpha^2 * log^2 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 m^{3/8 - epsilon}, for any constant epsilon > 0. This covers much of the range of possible values for arboricity, as the arboricity of a general graph cannot exceed m^{1/2}.

BibTeX - Entry

@InProceedings{onak_et_al:LIPIcs:2018:9096,
  author =	{Krzysztof Onak and Baruch Schieber and Shay Solomon and Nicole Wein},
  title =	{{Fully Dynamic MIS in Uniformly Sparse Graphs}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{92:1--92:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9096},
  URN =		{urn:nbn:de:0030-drops-90968},
  doi =		{10.4230/LIPIcs.ICALP.2018.92},
  annote =	{Keywords: dynamic graph algorithms, independent set, sparse graphs, graph arboricity}
}

Keywords: dynamic graph algorithms, independent set, sparse graphs, graph arboricity
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI