2021/01/01 by Yong Gu, Hanlin Ren
Computer Science · Engineering · Mathematics · #Combinatorics #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Computer science #Data Management and Algorithms #Engineering #Mathematics #Oracle #Programming language #Sensitivity (control systems) #cs.DS
paper · pdf · doi:10.4230/lipics.icalp.2021.76
accepted to ICALP 2021
openalex publication_date 2021/01/01 · openalex created_date 2021/03/01 · arxiv created 2021/08/03 · arxiv updated 2021/08/04 · openalex updated_date 2026/08/05
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(n2.5794M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n2.7233M), and even in the easier case of undirected graphs, the best preprocessing time is O(n2.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 xr. 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(n2.5286M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n2.6865M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing all-pairs shortest paths.