Simple and Faster algorithm for Reachability in a Decremental Directed Graph

Consider the problem of maintaining source sink reachability($st$-Reachability), single source reachability(SSR) and strongly connected component(SCC) in an edge decremental directed graph. In particular, we design a randomized algorithm that maintains with high probability:

1. $st$-Reachability in $\tilde{O}(m{n}^{4\mathrm{/}5})$ total update time. 2) $st$-Reachability in a total update time of $\tilde{O}(n^{8\mathrm{/}3})$ in a dense graph. 3) SSR in a total update time of $\tilde{O}(m{n}^{9\mathrm{/}10})$. 4) SCC in a total update time of $\tilde{O}(m{n}^{9\mathrm{/}10})$. For all the above problems, we improve upon the previous best algorithm (by Henzinger et. al. (STOC 2014)). Our main focus is maintaining $st$-Reachability in an edge decremental directed graph (other problems can be reduced to $st$-Reachability). The classical algorithm of Even and Shiloach (JACM 81) solved this problem in $O(1)$ query time and $O(mn)$ total update time. Recently, Henzinger, Krinninger and Nanongkai (STOC 2014) designed a randomized algorithm which achieves an update time of $\tilde{O}(m{n}^{0.98})$ and broke the long-standing $O(mn)$ bound of Even and Shiloach. However, they designed four algorithms $A_i (1\le i \le 4)$suchthatforgraphshavingtotalnumberofedgesbetween$m_i$and$m_{i+1}$($m_{i+1} > m_i$),$A_i$ outperforms other three algorithms. That is, one of the four algorithms may be faster for a particular density range of edges, but it may be too slow asymptotically for the other ranges. Our main contribution is that we design a {\it single} algorithm which works for all types of graphs. Not only is our algorithm faster, it is much simpler than the algorithm designed by Henzinger et.al. (STOC 2014).