Decremental strongly-connected components and single-source reachability in near-linear time

Aaron Bernstein, Maximilian Probst, Christian Wulff-Nilsen

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

21 Scopus citations

Abstract

Computing the Strongly-Connected Components (SCCs) in a graph G = (V, E) is known to take only O(m + n) time using an algorithm by Tarjan from 1972[SICOMP 72] where m = |E|, n = |V |. For fully-dynamic graphs, conditional lower bounds provide evidence that the update time cannot be improved by polynomial factors over recomputing the SCCs from scratch after every update. Nevertheless, substantial progress has been made to find algorithms with fast update time for decremental graphs, i.e. graphs that undergo edge deletions. In this paper, we present the first algorithm for general decremental graphs that maintains the SCCs in total update time Õ(m)1, thus only a polylogarithmic factor from the optimal running time. Previously such a result was only known for the special case of planar graphs [Italiano et al, STOC 17]. Our result should be compared to the formerly best algorithm for general graphs achieving Õ(mn) total update time by Chechik et.al. [FOCS 16] which improved upon a breakthrough result leading to O(mn0.9+o(1)) total update time by Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]; these results in turn improved upon the longstanding bound of O(mn) by Roditty and Zwick [STOC 04]. All of the above results also apply to the decremental Single-Source Reachability (SSR) problem, which can be reduced to decrementally maintaining SCCs. A bound of O(mn) total update time for decremental SSR was established already in 1981 by Even and Shiloach [JACM 81].

Original languageEnglish (US)
Title of host publicationSTOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
EditorsMoses Charikar, Edith Cohen
PublisherAssociation for Computing Machinery
Pages365-376
Number of pages12
ISBN (Electronic)9781450367059
DOIs
StatePublished - Jun 23 2019
Event51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 - Phoenix, United States
Duration: Jun 23 2019Jun 26 2019

Publication series

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

Conference

Conference51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019
Country/TerritoryUnited States
CityPhoenix
Period6/23/196/26/19

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamic algorithm
  • Single source reachability
  • Strongly connected components

Fingerprint

Dive into the research topics of 'Decremental strongly-connected components and single-source reachability in near-linear time'. Together they form a unique fingerprint.

Cite this