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

Understand

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.