Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths

Abstract

A distance sensitivity oracle is a data structure which, given two nodes s and t in a directed edge-weighted graph G and an edge e, returns the shortest length of an s-t path not containing e, a so called replacement path for the triple (s, t, e). Such oracles are used to quickly recover from edge failures. In this paper we consider the case of integer weights in the interval [-M, M], and present the first distance sensitivity oracle that achieves simultaneously subcubic preprocessing time and sublinear query time. More precisely, for a given parameter α ∈ [0, 1], our oracle has preprocessing time Õ(Mn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ω+1/2</sup> +Mn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ω+α(4-ω)</sup> ) and query time Õ(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-α</sup> ). Here w <; 2.373 denotes the matrix multiplication exponent. For a comparison, the previous best oracle for small integer weights has Õ(Mn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ω+1-α</sup> ) preprocessing time and (superlinear) Õ(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1+α</sup> ) query time [Weimann, Yuster-FOCS'10]. The main novelty in our approach is an algorithm to compute all the replacement paths from a given source s, an interesting problem on its own. We can solve the latter single-source replacement paths problem in Õ(APSP(n, M))) time, where APSP(n, M) <; Õ(M <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">0.681</sup> n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2.575</sup> ) [Zwick-JACM'02] is the runtime for computing all-pairs shortest paths in a graph with n vertices and integer edge weights in [-M, M]. For positive weights the runtime of our algorithm reduces to Õ(Mn <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ω</sup> ). This matches the best known runtime for the simpler replacement paths problem in which both the source s and the target t are fixed [Vassilevska-SODA'11].