Improved dynamic algorithms for maintaining approximate shortest paths under deletions

Abstract

We present the first dynamic shortest paths algorithms that make any progress beyond a longstanding O(n) update time barrier (while maintaining a reasonable query time), although it is only progress for not-too-sparse graphs. In particular, we obtain new decremental algorithms for two approximate shortest-path problems in unweighted, undirected graphs. Both algorithms are randomized (Las Vegas). • Given a source s, we present an algorithm that maintains (1 + ɛ)-approximate shortest paths from s with an expected total update time of Õ(n 2+O(1/ √ log n)) over all deletions (so the amortized time is about Õ(n2 /m)). The worstcase