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 α if it always holds that , where δG–D(u, v) is the actual distance between u and v in G – D, and is the distance reported by the oracle. In this paper we construct efficient VSDOs for any number d of failures. For any constant c ≥ 1, we propose two oracles: The first oracle has size n2+1/c(log n/∊)O(d) · log W, answers a query in poly(log n, dc, log log W, ∊–1) time, and has stretch 1 + ∊, for any constant ∊ > 0. The second oracle has size n2+1/cpoly (log(nW), d), answers a query in poly (log n, dc, log log W) time, and has stretch 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 + ∊)-approximate d-edge sensitive distance oracles [Chechik et al. 2017] answering distance queries when d edges fail, which have size O(n2(log n/∊)d · d log W) and query time poly (log n, d, log log W).