Maintaining shortest paths under deletions in weighted directed graphs

We present an improved algorithm for maintaining all-pairs (1 + ϵ) approximate shortest paths under deletions and weight-increases. The previous state of the art for this problem is total update time ϵ O(n² √m/ϵ) over all updates for directed unweighted graphs [S. Baswana, R. Hariharan, and S. Sen, J. Algorithms, 62 (2007), pp. 74.92], and ϵ O(mn/ϵ) for undirected unweighted graphs [L. Roditty and U. Zwick, in Proceedings of the 45th FOCS, Rome, Italy, 2004, pp. 499.508]. Both algorithms are randomized and have constant query time. Very recently, Henzinger, Krinninger, and Nanongkai presented a deterministic version of the latter algorithm [M. Henzinger, S. Krinninger, and D. Nanongkai, in IEEE FOCS, 2013, pp. 538.547]. Note that ϵ O(mn) is a natural barrier because even with a (1 + ϵ) approximation, there is no o(mn) combinatorial algorithm for the static all-pairs shortest path problem. Our algorithm works on directed weighted graphs and has total (randomized) update time ϵ O(mn log R/ϵ) where R is the ratio of the largest edge weight to appear at any point in the update sequence to the smallest such weight. (As with previous algorithms, our query time is constant.) Technically, the running time is ϵ O(mnlog R/ϵ) + O(δ), where δ is the total number of updates; the same O(δ) term is also implicitly present in all other algorithms for the problem, since a constant time per update is clearly unavoidable. Note that logR = O(log(n)) as long as weights are polynomial in n; thus, we effectively expand the ϵ O(mn/ϵ) total update time bound from undirected unweighted graphs to directed graphs with polynomial weights. This is in fact the first nontrivial algorithm for decremental all-pairs shortest paths that works on weighted graphs (previous algorithms could only handle small integer weights). By a well-known reduction from decremental algorithms to fully dynamic ones [M. Henzinger and V. King, in Proceedings of the 36th FOCS, Milwaukee, WI, 1995, pp. 664.672], our improved decremental algorithm leads to improved query-update trade-offs for fully dynamic (1 + ϵ) approximate all-pairs shortest paths (APSP) algorithms in directed graphs.