## 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^{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.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Association for Computing Machinery (ACM) |

Pages | 742-755 |

Number of pages | 14 |

ISBN (Print) | 9780898717013 |

DOIs | |

State | Published - 2010 |

Event | 21st Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, United States Duration: Jan 17 2010 → Jan 19 2010 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 21st Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country/Territory | United States |

City | Austin, TX |

Period | 1/17/10 → 1/19/10 |

## ASJC Scopus subject areas

- Software
- General Mathematics