Approximate Distance Oracles Subject to Multiple Vertex Failures

Given an undirected graph $G=(V,E)$ of $n$ vertices and $m$ edges with weights in $[1,W]$, we construct vertex sensitive distance oracles (VSDO), which are data structures that preprocess the graph, and answer the following kind of queries: Given a source vertex $u$, a target vertex $v$, and a batch of $d$ failed vertices $D$, output (an approximation of) the distance between $u$ and $v$ in $G-D$ (that is, the graph $G$ with vertices in $D$ removed). An oracle has stretch $\alpha$ if it always holds that ${\delta }_{G-D}(u,v)\le \tilde{\delta }(u,v)\le \alpha \cdot {\delta }_{G-D}(u,v)$, where ${\delta }_{G-D}(u,v)$ is the actual distance between $u$ and $v$ in $G-D$, and $\tilde{\delta }(u,v)$ is the distance reported by the oracle. In this paper we construct efficient VSDOs for any number $d$ of failures. For any constant $c\ge 1$, we propose two oracles: $\bullet$ The first oracle has size $n^{2+1/c}(\log n/\epsilon)^{O(d)}\cdot \log W$,answersaqueryin${\rm poly}(\log n,d^c,\log\log W,\epsilon^{-1})$time,andhasstretch$1+\epsilon$,foranyconstant$\epsilon>0$\mathrm{.}$\bullet$Thesecondoraclehassize$n^{2+1/c}{\rm poly}(\log (nW),d)$, answers a query in $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log n,d^c,\log \log W)$ time, and has stretch $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(\log n,d)$. Both of these oracles can be preprocessed in time polynomial in their space complexity. These results are the first approximate distance oracles of poly-logarithmic query time for any constant number of vertex failures in general undirected graphs. Previously there are $(1+ϵ)$-approximate $d$-edge sensitive distance oracles [Chechik et al. 2017] answering distance queries when $d$ edges fail, which have size $O(n^2(\log n/\epsilon)^d\cdot d\log W)$andquerytime${\rm poly}(\log n, d, \log\log W)$.