Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
Preprint
Abstract
In the Single Source Replacement Paths (SSRP) problem we are given a graph $G = (V, E)$, and a shortest paths tree $\widehat{K}$ rooted at a node $s$, and the goal is to output for every node $t \in V$ and for every edge $e$ in $\widehat{K}$ the length of the shortest path from $s$ to $t$ avoiding $e$. We present an $\tilde{O}(m\sqrt{n} + n^2)$ time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm extends to the case of small, rational edge weights. We strengthen the existing conditional lower bounds in this case by showing that any $O(mn^{1/2-\epsilon})$ time (combinatorial or algebraic) algorithm for some fixed $\epsilon >0$ yields a truly subcubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting).
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- Replacement paths and k simple shortest paths in unweighted directed graphsACM Transactions on Algorithms, 2012
- Finding the most vital node of a shortest pathTheoretical Computer Science, 2003
- All pairs shortest paths using bridging sets and rectangular matrix multiplicationJournal of the ACM, 2002
- A faster computation of the most vital edge of a shortest pathInformation Processing Letters, 2001
- Finding the k Shortest PathsSIAM Journal on Computing, 1998
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest PathsSIAM Journal on Computing, 1993
- The k most vital arcs in the shortest path problemOperations Research Letters, 1989
- An algorithm for finding all shortest paths using N2.81 infinite-precision multiplicationsInformation Processing Letters, 1976