Improved distance sensitivity oracles via random sampling

We present improved oracles for the distance sensitivity problem. The goal is to preprocess a graph G = (V,E) with non-negative edge weights to answer queries of the form: what is the length of the shortest path from × to y that does not go through some failed vertex or edge f. There are two state of the art algorithms for this problem. The first produces an oracle of size Õ(n ²) that has an O(1) query time, and an Õ(mn ²) construction time. The second oracle has size O(n ^2.5), but the construction time is only Õ(mn ^1.5). We present two new oracles that substantially improve upon both of these results. Both oracles are constructed with randomized, Monte Carlo algorithms. For directed graphs with non-negative edge weights, we present an oracle of size Õ(n ²), which has an O(1) query time, and an Õ(n ² √m) construction time. For unweighted graphs, we achieve a more general construction time of Õ(√n ³ · APSP + mn), where APSP is the time it takes to compute all pairs shortest paths in an aribtrary subgraph of G.