## March 17, 2017:

#
Improved Algorithms for Decremental Single-Source Reachability on
Directed Graphs

##
Sid Gupta

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 = \Theta(n^{1.5})$ the running time is $O(n^{2.47})$,
just barely below $mn = \Theta(n^{2.5})$. In this paper we simplify
the previous algorithm using new algorithmic ideas and achieve an
improved running time of $\tilde O(\min(m^{7/6} n^{2/3}, m^{3/4}
n^{5/4 + o(1)}, m^{2/3} n^{4/3+o(1)} + m^{3/7} n^{12/7+o(1)}))$. 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)