In the dynamic shortest paths problem, the goal is to maintain shortest path information in a graph whose edges are being inserted or deleted over time. More formally, we must process an online sequence of update and query operations, where an update operation inserts or deletes an edge from the underlying graph, while a query operation asks for the shortest distance/path between two vertices. We focus on the decremental version, in which edges are only deleted, never inserted. There exist many different algorithms for this problem, both exact and approximate, but even with approximation all of these algorithm stop at a natural barrier of an O(n) amortized update time. We present the first two algorithms to break through this barrier. Both are for unweighted, undirected graphs.

For single source shortest paths, we present a (1 + epsilon) approximation algorithm with amortized update time around O(n^2/m) (a bit worse). For all pairs shortest paths, we achieve a trade-off between update time and approximation error. For example, our framework achieves a (3 + epsilon)-approximation with an amortized update time of about O(n^{2.5}/m). The key to our algorithms is a general technique for accelerating decremental algorithms; we achieve our results by applying the technique to two particular decremental algorithms, but it could be applied to others as they come up.