# Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2016.

## 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)

Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with o(mn) total update time, where m is the number of edges and n is the number of nodes in the graph [Henzinger et al. STOC 2014]. The algorithm is a combination of several different algorithms, each for a different m vs. n trade-off. For the case of m = Theta(n1.5) the running time is O(n2.47), just barely below mn = Theta(n2.5). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of tilde O(min(m7/6 n2/3, m3/4 n5/4 + o(1), m2/3 n4/3+o(1) + m3/7 n12/7+o(1))). This gives, e.g., O(n2.36) for the notorious case m = Theta(n1.5). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.