Improved Distance Sensitivity Oracles with Subcubic Preprocessing Time

We consider the problem of building Distance Sensitivity Oracles (DSOs). Given a directed graph G=(V, E) with edge weights in 1, 2, dots, M, we need to preprocess it into a data structure, and answer the following queries: given vertices u,v∈ V and a failed vertex or edge f∈ (Vcup E), output the length of the shortest path from u to v that does not go through f. Our main result is a simple DSO with tildeO(n2.7233M) preprocessing time and O(1) query time. Moreover, if the input graph is undirected, the preprocessing time can be improved to tildeO(n2.6865M). The preprocessing algorithm is randomized with correct probability ≥ 1-1/nC, for a constant C that can be made arbitrarily large. Previously, there is a DSO with tildeO(n2.8729M) preprocessing time and operatornamepolylog(n) query time [Chechik and Cohen, STOC'20]. At the core of our DSO is the following observation from [Bernstein and Karger, STOC'09]: if there is a DSO with preprocessing time P and query time Q, then we can construct a DSO with preprocessing time P+tildeO(n2)· Q and query time O(1). (Here tildeO(·) hides operatornamepolylog(n) factors.)