Constructing a Distance Sensitivity Oracle in O(n^2.5794M) Time
share
We continue the study of distance sensitivity oracles (DSOs). Given a directed graph G with n vertices and edge weights in {1, 2, …, M}, we want to build a data structure such that given any source vertex u, any target vertex v, and any failure f (which is either a vertex or an edge), it outputs the length of the shortest path from u to v not going through f. Our main result is a DSO with preprocessing time O(n^2.5794M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n^2.7233M), and even in the easier case of undirected graphs, the best preprocessing time is O(n^2.6865M) [Ren, ESA 2020]. One drawback of our DSOs, though, is that it only supports distance queries but not path queries. Our main technical ingredient is an algorithm that computes the inverse of a degree-d polynomial matrix (i.e. a matrix whose entries are degree-d univariate polynomials) modulo x^r. The algorithm is adapted from [Zhou, Labahn and Storjohann, Journal of Complexity, 2015], and we replace some of its intermediate steps with faster rectangular matrix multiplication algorithms. We also show how to compute unique shortest paths in a directed graph with edge weights in {1, 2, …, M}, in O(n^2.5286M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n^2.6865M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.
READ FULL TEXT