A nearly optimal oracle for avoiding failed vertices and edges

Abstract

We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from x to y that does not go through some failed vertex or edge f. The previous best algorithm produces an oracle of size ~O(n2) that has an O(1) query time, and an ~O(n2√m) construction time. It was a randomized Monte Carlo algorithm that worked with high probability. Our oracle also has a constant query time and an ~O(n2) space requirement, but it has an improved construction time of ~O(mn), and it is deterministic. Note that O(1) query, O(n2) space, and O(mn) construction time is also the best known bound (up to logarithmic factors) for the simpler problem of finding all pairs shortest paths in a weighted, directed graph. Thus, barring improved solutions to the all pairs shortest path problem, our oracle is optimal up to logarithmic factors.