Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Conference: European Symposium on Algorithms 2021
Speaker: Martin Schirneck
Abstract: A single-source distance sensitivity oracle (single-source DSO) preprocesses a given graph \(G\) with a distinguished source vertex \(s\) into a data structure. When queried with a target vertex \(t\) and an edge \(e\), the structure reports the replacement distance \(d_{G-e}(s,t)\) in case \(e\) fails. In the closely related single-source replacement paths (SSRP) problem, we are given \(G\) and \(s\) and have to enumerate all distances \(d_{G-e}(s,t)\).
We present deterministic single-source DSOs for undirected graphs with \(\widetilde{O}(1)\) query time. For unweighted graphs, we give a combinatorial preprocessing algorithm running in time \(\widetilde{O}(m \sqrt{n} + n^2)\), resulting in a data structure taking \(O(n^{3/2})\) space. For graphs with integer edge weights in the range \([1,M]\) and when using fast matrix multiplication, we get a preprocessing time of \(\widetilde{O}(Mn^{\omega})\), and the oracle takes \(O(M^{1/2}n^{3/2})\) space. Here, \(\omega < 2.373\) denotes the matrix multiplication exponent. Both preprocessing times improve over previous constructions by polynomial factors. We further show that the space requirement is optimal up to the size of a machine word. Finally, we give a randomized preprocessing algorithm that breaks the quadratic barrier on sufficiently sparse graphs.
We obtain our oracles by derandomizing known SSRP algorithms by Chechik & Cohen [SODA'19] as well as Grandoni & Vassilevska Williams [FOCS'12] and combining them with a novel compression scheme for replacement distances.
This is joined work with Davide Bilò, Sarel Cohen and Tobias Friedrich.