A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
Aaron Bernstein · 2010
Let G = (V, E) be a directed graph with positive edge weights, let s, t be two specified vertices in this graph, and let π(s, t) be the shortest path between them. In the replacement paths problem we want to compute, for every edge e on π(s, t), the shortest path from s to t that avoids e. The naive solution to this problem would be to remove each edge e, one at a time, and compute the shortest s − t path each time; this yields a running time of O(mn + n 2 log n). Gotthilf and Lewenstein [8] recently improved this to O(mn+n 2 log log n), but no o(mn) algorithms are known. We present the first approximation algorithm for replacement paths in directed graphs with positive edge weights. Given any ɛ ∈ [0, 1), our algorithm returns (1 + ɛ)-approximate replacement paths in O(ɛ −1 log 2 n log(nC/c)(m+n log n)) = Õ(m log(nC/c)/ɛ) time, where C is the largest edge weight in the graph and c is the smallest weight. We also present an even faster (1 + ɛ) approximate algorithm for the simpler problem of approximating the k shortest simple s − t paths in a directed graph with positive edge weights. That is, our algorithm outputs k different simple s−t paths, where the kth path we output is a (1 + ɛ) approximation to the actual kth shortest simple s − t path. The running time of our algorithm is O(kɛ −1 log 2 n(m + n log n)) = Õ(km/ɛ). The fastest exact algorithm for this problem has a running time of O(k(mn+n 2 log log n)) = Õ(kmn) [8]. The previous best approximation algorithm was developed by Roditty [15]; it has a stretch of 3/2 and a running time of Õ(km√n) (it does not work for replacement paths). Note that all of our running times are nearly optimal except for the O(log(nC/c)) factor in the replacements paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges. 1