Approximate Distance Oracles Subject to Multiple Vertex Failures
share
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 δ_G-D(u,v)<δ̃(u,v)<α·δ_G-D(u,v), where δ_G-D(u,v) is the actual distance between u and v in G-D, and δ̃(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≥ 1, we propose two oracles: * The first oracle has size n^2+1/c(log n/ϵ)^O(d)·log W, answers a query in poly(log n,d^c,loglog W,ϵ^-1) time, and has stretch 1+ϵ, for any constant ϵ>0. * The second oracle has size n^2+1/c poly(log (nW),d), answers a query in poly(log n,d^c,loglog 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(n^2(log n/ϵ)^d· dlog W) and query time poly(log n, d, loglog W).
READ FULL TEXT