Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
Research output: Contribution to journal › Journal article › Research › peer-review
Standard
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time. / Bernstein, Aaron; Gutenberg, Maximilian Probst; Wulff-Nilsen, Christian.
In: SIAM Journal on Computing, Vol. 52, No. 2, 2023, p. 128-155.Research output: Contribution to journal › Journal article › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
AU - Bernstein, Aaron
AU - Gutenberg, Maximilian Probst
AU - Wulff-Nilsen, Christian
N1 - Publisher Copyright: © 2021 Society for Industrial and Applied Mathematics.
PY - 2023
Y1 - 2023
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 [SIAM J. Comput., 1 (1972), pp. 146-160] 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), thus only a polylogarithmic factor from the optimal running time. (We use O(f(n)) notation to suppress logarithmic factors, i.e., g(n) = O(f(n)) if g(n) = O(f(n)polylog(n)).) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs S × V , S ⊆ V in fully dynamic graphs with update time O(|S|mt) and query time O(t) for all t ∊ [1, |S|]; this matches to polylogarithmic factors the best all-pairs reachability algorithm for S = V .
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 [SIAM J. Comput., 1 (1972), pp. 146-160] 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), thus only a polylogarithmic factor from the optimal running time. (We use O(f(n)) notation to suppress logarithmic factors, i.e., g(n) = O(f(n)) if g(n) = O(f(n)polylog(n)).) Our result also yields the fastest algorithm for the decremental single-source reachability (SSR) problem which can be reduced to decrementally maintaining SCCs. Using a well-known reduction, we use our decremental result to achieve new update/query-time trade-offs in the fully dynamic setting. We can maintain the reachability of pairs S × V , S ⊆ V in fully dynamic graphs with update time O(|S|mt) and query time O(t) for all t ∊ [1, |S|]; this matches to polylogarithmic factors the best all-pairs reachability algorithm for S = V .
KW - data structures
KW - dynamic graph algorithms
KW - ES-tree
KW - reachability
KW - single-source reachability
KW - strongly connected components
UR - http://www.scopus.com/inward/record.url?scp=85159764742&partnerID=8YFLogxK
U2 - 10.1137/20M1312149
DO - 10.1137/20M1312149
M3 - Journal article
AN - SCOPUS:85159764742
VL - 52
SP - 128
EP - 155
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
SN - 0097-5397
IS - 2
ER -
ID: 355112729