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

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Standard

Decremental strongly-connected components and single-source reachability in near-linear time. / Bernstein, Aaron; Probst, Maximilian; Wulff-Nilsen, Christian.

STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. red. / Moses Charikar; Edith Cohen. Association for Computing Machinery, 2019. s. 365-376 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Publikation: Bidrag til bog/antologi/rapportKonferencebidrag i proceedingsForskningfagfællebedømt

Harvard

Bernstein, A, Probst, M & Wulff-Nilsen, C 2019, Decremental strongly-connected components and single-source reachability in near-linear time. i M Charikar & E Cohen (red), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, Proceedings of the Annual ACM Symposium on Theory of Computing, s. 365-376, 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, USA, 23/06/2019. https://doi.org/10.1145/3313276.3316335

APA

Bernstein, A., Probst, M., & Wulff-Nilsen, C. (2019). Decremental strongly-connected components and single-source reachability in near-linear time. I M. Charikar, & E. Cohen (red.), STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (s. 365-376). Association for Computing Machinery. Proceedings of the Annual ACM Symposium on Theory of Computing https://doi.org/10.1145/3313276.3316335

Vancouver

Bernstein A, Probst M, Wulff-Nilsen C. Decremental strongly-connected components and single-source reachability in near-linear time. I Charikar M, Cohen E, red., STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery. 2019. s. 365-376. (Proceedings of the Annual ACM Symposium on Theory of Computing). https://doi.org/10.1145/3313276.3316335

Author

Bernstein, Aaron ; Probst, Maximilian ; Wulff-Nilsen, Christian. / Decremental strongly-connected components and single-source reachability in near-linear time. STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. red. / Moses Charikar ; Edith Cohen. Association for Computing Machinery, 2019. s. 365-376 (Proceedings of the Annual ACM Symposium on Theory of Computing).

Bibtex

@inproceedings{21656ad6c8c2414b99eb4e2898c058fd,
title = "Decremental strongly-connected components and single-source reachability in near-linear time",
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 {\~O}(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 {\~O}(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].",
keywords = "Dynamic algorithm, Single source reachability, Strongly connected components",
author = "Aaron Bernstein and Maximilian Probst and Christian Wulff-Nilsen",
year = "2019",
doi = "10.1145/3313276.3316335",
language = "English",
series = "Proceedings of the Annual ACM Symposium on Theory of Computing",
publisher = "Association for Computing Machinery",
pages = "365--376",
editor = "Moses Charikar and Edith Cohen",
booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",
note = "51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

}

RIS

TY - GEN

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

AU - Bernstein, Aaron

AU - Probst, Maximilian

AU - Wulff-Nilsen, Christian

PY - 2019

Y1 - 2019

N2 - 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].

AB - 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].

KW - Dynamic algorithm

KW - Single source reachability

KW - Strongly connected components

U2 - 10.1145/3313276.3316335

DO - 10.1145/3313276.3316335

M3 - Article in proceedings

AN - SCOPUS:85068764114

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 365

EP - 376

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019

Y2 - 23 June 2019 through 26 June 2019

ER -

ID: 239207274