Logo der Universität Wien

Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs


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 which, in a simplified form, achieves an \tilde O(mn^{0.984}) expected total update time for SSSR and (1+ε)-approximate SSSP, where \tilde O(·) hides polylog n. 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), and an algorithm that improves the \tilde O(mnlogW)-time algorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case.

Paper in Conference Proceedings or in Workshop Proceedings (Full Paper in Proceedings)
Event Title
46th ACM Symposium on Theory of Computing (STOC 2014)
Theory and Applications of Algorithms
Theoretische Informatik
Event Location
New York, NY, USA
Event Type
Event Dates
June 1 – June 3, 2014
June 2014
Contact us
Faculty of Computer Science
University of Vienna

Währinger Straße 29
A-1090 Vienna