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}(mn^{4/5})$ total update time. 2) $st$-Reachability in a total update time of $\tilde{O}(n^{8/3})$ in a dense graph. 3) SSR in a total update time of $\tilde{O}(m n^{9/10})$. 4) SCC in a total update time of $\tilde{O}(m n^{9/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)$ such that for graphs having total number of edges between $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).

No reviews yet.

No comments yet.