# Approximate Distance Oracles Subject to Multiple Vertex Failures

Research paper by **Ran Duan, Yong Gu, Hanlin Ren**

Indexed on: **18 Feb '20**Published on: **17 Feb '20**Published in: **arXiv - Computer Science - Data Structures and Algorithms**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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\geq 1$, we propose two oracles:
* The first oracle has size $n^{2+1/c}(\log n/\epsilon)^{O(d)}\cdot \log W$,
answers a query in ${\rm poly}(\log n,d^c,\log\log W,\epsilon^{-1})$ time, and
has stretch $1+\epsilon$, for any constant $\epsilon>0$.
* The second oracle has size $n^{2+1/c}{\rm poly}(\log (nW),d)$, answers a
query in ${\rm poly}(\log n,d^c,\log\log W)$ time, and has stretch ${\rm
poly}(\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+\epsilon)$-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)$ and query time ${\rm poly}(\log n, d, \log\log W)$.