SODA Conference 2021 Conference Paper
Approximate Distance Oracles Subject to Multiple Vertex Failures
- Ran Duan
- Yong Gu
- Hanlin Ren
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 n 2+1/ c (log n/∊ ) O ( d ) · log W, answers a query in poly(log n, d c, log log 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, 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 ( n 2 (log n/∊ ) d · d log W ) and query time poly (log n, d, log log W ).