Abstract
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.5794 M) and constant query time. Previously, the best preprocessing time of DSOs for directed graphs is O(n^2.7233 M), and even in the easier case of undirected graphs, the best preprocessing time is O(n^2.6865 M) [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 degreed polynomial matrix (i.e. a matrix whose entries are degreed 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.5286 M) time. This algorithm is crucial in the preprocessing algorithm of our DSO. Our solution improves the O(n^2.6865 M) time bound in [Ren, ESA 2020], and matches the current best time bound for computing allpairs shortest paths.
BibTeX  Entry
@InProceedings{gu_et_al:LIPIcs.ICALP.2021.76,
author = {Gu, Yong and Ren, Hanlin},
title = {{Constructing a Distance Sensitivity Oracle in O(n^2.5794 M) Time}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {76:176:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14145},
URN = {urn:nbn:de:0030drops141450},
doi = {10.4230/LIPIcs.ICALP.2021.76},
annote = {Keywords: graph theory, shortest paths, distance sensitivity oracles}
}
Keywords: 

graph theory, shortest paths, distance sensitivity oracles 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 