  We consider dynamic algorithms for maintaining Single-Source Reachability
(SSR) and approximate Single-Source Shortest Paths (SSSP) on $n$-node $m$-edge
directed graphs under edge deletions (decremental algorithms). The previous
fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach
[JACM 1981]; it has $ O(1) $ query time and $ O (mn) $ total update time (i.e.,
linear amortized update time if all edges are deleted). This algorithm serves
as a building block for several other dynamic algorithms. The question whether
its total update time can be improved is a major, long standing, open problem.
  In this paper, we answer this question affirmatively. We obtain a randomized
algorithm with an expected total update time of $ O(\min (m^{7/6} n^{2/3 +
o(1)}, m^{3/4} n^{5/4 + o(1)}) ) = O (m n^{9/10 + o(1)}) $ for SSR and
$(1+\epsilon)$-approximate SSSP if the edge weights are integers from $ 1 $ to
$ W \leq 2^{\log^c{n}} $ and $ \epsilon \geq 1 / \log^c{n} $ for some constant
$ c $. We also extend our algorithm to achieve roughly the same running time
for Strongly Connected Components (SCC), improving the algorithm of Roditty and
Zwick [FOCS 2002]. Our algorithm is most efficient for sparse and dense graphs.
When $ m = \Theta(n) $ its running time is $ O (n^{1 + 5/6 + o(1)}) $ and when
$ m = \Theta(n^2) $ its running time is $ O (n^{2 + 3/4 + o(1)}) $. For SSR we
also obtain an algorithm that is faster for dense graphs and has a total update
time of $ O ( m^{2/3} n^{4/3 + o(1)} + m^{3/7} n^{12/7 + o(1)}) $ which is $ O
(n^{2 + 2/3}) $ when $ m = \Theta(n^2) $. All our algorithms have constant
query time in the worst case and are correct with high probability against an
oblivious adversary.
