Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

DOI10.1145/2591796.2591869zbMATH Open1315.68280arXiv1504.07959OpenAlexW3098654413MaRDI QIDQ5259603FDOQ5259603

Sebastian Krinninger, Danupon Nanongkai, Monika R. Henzinger

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: 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 (m n)

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 (m i n (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 + e p s i l o n)

-approximate SSSP if the edge weights are integers from

1

to

W l e q 2^{l o g^{c} n}

and

e p s i l o n g e q 1 / l o g^{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