Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn) total update time, where m is the number of edges and n is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different m vs. n trade-off. For the case of m = Theta(n1.5) the running time is O(n2.47), just barely below mn = Theta(n2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of tilde O(min(m7/6 n2/3, m3/4 n5/4 + o(1), m2/3 n4/3+o(1) + m3/7 n12/7+o(1))). This gives, e.g., O(n2.36) for the notorious case m = Theta(n1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.