Constructing Approximate Single-Source Distance Sensitivity Oracles in Nearly Linear Time

For an input graph $G=(V, E)$ and a source vertex $s \in V$, the \emph{$\alpha$-approximate vertex fault-tolerant distance sensitivity oracle} (\emph{$\alpha$-VSDO}) answers an $\alpha$-approximate distance from $s$ to $t$ in $G-x$ for any query $(x, t)$. It is a data structure version of the so-called single-source replacement path problem (SSRP). In this paper, we present a new \emph{nearly linear time} algorithm of constructing the $(1 + \epsilon)$-VSDO for any weighted directed graph of $n$ vertices and $m$ edges with integer weights in range $[1, W]$, and any positive constant $\epsilon \in (0, 1]$. More precisely, the presented oracle attains $\tilde{O}(m / \epsilon + n /\epsilon^2)$ construction time, $\tilde{O}(n/ \epsilon)$ size, and $\tilde{O}(1/\epsilon)$ query time for any polynomially-bounded $W$. To the best of our knowledge, this is the first non-trivial result for SSRP/VSDO beating the trivial $\tilde{O}(mn)$ computation time for directed graphs with polynomially-bounded edge weights. Such a result has been unknown so far even for the setting of $(1 + \epsilon)$-approximation. It also implies that the known barrier of $\Omega(m\sqrt{n})$ time for the exact SSRP by Chechik and Magen~[ICALP2020] does not apply to the case of approximation.