At STOC 2014, Henzinger et al. 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. The algorithm is a combination of several different algorithms, each for a different m vs. n trade-off. For the case of m=Θ(n1.5) the running time is O(n2.47), just barely below mn=Θ(n2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of ˜O(min. This gives, e.g., O(n^{2.36}) for the notorious case m = \Theta(n^{1.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.
(Based on a paper by Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai from ICALP 2015)