Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Indsendt manuskript, 376 KB, PDF-dokument
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 .
Originalsprog | Engelsk |
---|---|
Tidsskrift | SIAM Journal on Computing |
Vol/bind | 52 |
Udgave nummer | 2 |
Sider (fra-til) | 128-155 |
ISSN | 0097-5397 |
DOI | |
Status | Udgivet - 2023 |
Bibliografisk note
Funding Information:
\ast Received by the editors January 16, 2020; accepted for publication (in revised form) August 16, 2021; published electronically December 14, 2021. https://doi.org/10.1137/20M1312149 Funding: The work of the first author was supported by NSF CAREER award 1942010. The work of the second author was supported by ETH Zurich and partially by the Basic Algorithms Research Copenhagen (BARC), supported by Thorup's Investigator Grant from the Villum Foundation under grant 16582. The work of the third author was supported by BARC under Starting Grant 7027-00050B. \dagger Department of Computer Science, Rutgers University New Brunswick, Piscataway, NJ 08854-8019 USA (bernstei@gmail.com). \ddagger Department of Computer Science, ETH Zurich, Switzerland (maximilian.probst@outlook.com). \S Department of Computer Science, University of Copenhagen, and BARC, Copenhagen, Denmark (koolooz@diku.dk).
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics.
ID: 355112729