Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate

We present new algorithms for the vertex-failure distance oracles and labeling schemes problems in undirected weighted graphs. A vertex-failure distance oracle is a data structure that, given two vertices $x$ and $y$ and a failed vertex set $F$ of size at most $f$, returns an approximation to the distance between $x$ and $y$ in $G\setminus F$. In the labeling-scheme setting, the data structure needs to be stored distributively as labels on the vertices, and each query $(x,y,F)$ must be answered by accessing only the labels of the vertices in $F\cup \{x,y\}$. For any $f\ge 1$ and $k\ge 1$, we obtain a vertex-failure distance oracle with $O(k^6)$ approximation, space $\tilde{O}(f^2{n}^{1+1\mathrm{/}k})$, query time $\tilde{O}(f^5{n}^{1\mathrm{/}k})$, and polynomial preprocessing time. In particular, this is the first time-efficient oracle for multiple vertex failures with space close to linear, as well as the first constant-approximation oracle with polynomial space when tolerating $\mathrm{\Omega }(\log n)$ vertex failures. The previous results, due to [Duan-Gu-Ren, SODA’21], gave two alternatives: for any constant $c\ge 1$ and $\epsilon >0$, one oracle has $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log n,f)$ approximation, space $n^{2+1\mathrm{/}c}\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log n,f)$, and query time $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log n,f^c)$, while the other has $(1+\epsilon )$ approximation, space $n^{2+1\mathrm{/}c}(\log n\mathrm{/}\epsilon {)}^{O(f)}$, and query time $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log n,f^c,1\mathrm{/}\epsilon )$. We also obtain a vertex-failure distance labeling scheme with $O(k^6)$ approximation and label size $f^3{n}^{1\mathrm{/}k}{\log }^{O(k)}n$. This is the first nontrivial distance labeling scheme for vertex failures. Our techniques build on recent tools related to length-constrained vertex expanders and also introduce a new expander-based shortcut sparsification. The latter also leads to a deterministic vertex-failure connectivity labeling scheme of size $\tilde{O}(f^2)$.