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

arXiv: https://arxiv.org/abs/1504.07959 · HTML: https://mlsanity.com/paper/1504.07959/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2015.

## Built on by (most cited first, 2 of 2)

- [Incremental Approximate Single-Source Shortest Paths with Predictions](https://mlsanity.com/paper/2502.08125/) (2025)
- [Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation](https://mlsanity.com/paper/2505.03955/) (2025)

## Abstract (arXiv)

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 (m7/6 n2/3 + o(1), m3/4 n5/4 + o(1)) ) = O (m n9/10 + o(1))  for SSR and (1+ε)-approximate SSSP if the edge weights are integers from  1  to  W ≤ 2^logcn  and  ε ≥ 1 / logcn  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 (n1 + 5/6 + o(1))  and when  m = Theta(n2)  its running time is  O (n2 + 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 ( m2/3 n4/3 + o(1) + m3/7 n12/7 + o(1))  which is  O (n2 + 2/3)  when  m = Theta(n2) . All our algorithms have constant query time in the worst case and are correct with high probability against an oblivious adversary.