License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.68
URN: urn:nbn:de:0030-drops-187211
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18721/
Go to the corresponding LIPIcs Volume Portal

Karczmarz, Adam ; Smulewicz, Marcin

On Fully Dynamic Strongly Connected Components

pdf-format:
LIPIcs-ESA-2023-68.pdf (0.7 MB)

Abstract

We consider maintaining strongly connected components (SCCs) of a directed graph subject to edge insertions and deletions. For this problem, we show a randomized algebraic data structure with conditionally tight O(n^1.529) worst-case update time. The only previously described subquadratic update bound for this problem [Karczmarz, Mukherjee, and Sankowski, STOC'22] holds exclusively in the amortized sense.
For the less general dynamic strong connectivity problem, where one is only interested in maintaining whether the graph is strongly connected, we give an efficient deterministic black-box reduction to (arbitrary-pair) dynamic reachability. Consequently, for dynamic strong connectivity we match the best-known O(n^1.407) worst-case upper bound for dynamic reachability [van den Brand, Nanongkai, and Saranurak FOCS'19]. This is also conditionally optimal and improves upon the previous O(n^1.529) bound. Our reduction also yields the first fully dynamic algorithms for maintaining the minimum strong connectivity augmentation of a digraph.

BibTeX - Entry

@InProceedings{karczmarz_et_al:LIPIcs.ESA.2023.68,
  author =	{Karczmarz, Adam and Smulewicz, Marcin},
  title =	{{On Fully Dynamic Strongly Connected Components}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{68:1--68:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18721},
  URN =		{urn:nbn:de:0030-drops-187211},
  doi =		{10.4230/LIPIcs.ESA.2023.68},
  annote =	{Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability}
}

Keywords: dynamic strongly connected components, dynamic strong connectivity, dynamic reachability
Collection: 31st Annual European Symposium on Algorithms (ESA 2023)
Issue Date: 2023
Date of publication: 30.08.2023

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