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

• DOI: 10.1145/3313276.3316335
• Publication Date: 2019-06-20T12:19:08Z
• Authors: Aaron Bernstein; Maximilian Probst; Christian Wulff-N...
• Keywords: Strongly connected component; Scratch

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 update cannot be improved polynomial factors over recomputing SCCs scratch after every update. Nevertheless, substantial progress has been made find algorithms with fast for decremental i.e. graphs undergo edge deletions.