research-article

A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs

Author:

Aaron BernsteinAuthors Info & Claims

SODA '10: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete algorithms

Pages 742 - 755

Published: 17 January 2010 Publication History

Get Access

Abstract

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² log n). Gotthilf and Lewenstein [8] recently improved this to O(mn+n² 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² 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² n(m + n log n)) = Õ(km/ε). The fastest exact algorithm for this problem has a running time of O(k(mn+n² 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.

References

[1]

A. Bernstein and D. Karger, Improved distance sensitivity oracles via random sampling, in Proc. of the 19th SODA, San Francisco, California, 2008, pp. 34--43.

Abstract

References

Cited By

Recommendations

Replacement paths and k simple shortest paths in unweighted directed graphs

A deterministic almost-tight distributed algorithm for approximating single-source shortest paths

Improved algorithms for the k simple shortest paths and the replacement paths problems

Comments

Information

Published In

Sponsors

Publisher

Publication History

Check for updates

Qualifiers

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations