Vertex-failure distance oracles enable compact approximate routing after multiple failures
Vertex-Failure Distance Oracles and Labeling Schemes: Compact and Constant-Approximate
Data Structures and Algorithms
Summary
This work addresses the problem of quickly estimating distances between points in a network even when some points fail. The authors developed new data structures that can handle multiple failed points and still give approximate distances efficiently, using far less storage than before. They also created a way to store this information distributedly across the network's nodes, enabling local querying with small labels. Their approach improves on prior methods in speed, space needed, and the number of failures tolerated.
What this means in practice
- •For network operators: Maintain fast approximate routing adjustments in communication networks after multiple node failures using compact data structures.
- •For distributed system engineers: Use distributed vertex labels to quickly estimate distances locally even when some components fail, improving resilience in large systems.
Authors
Yaowei Long
Abstract
We present new algorithms for the vertex-failure distance oracles and labeling schemes problems in undirected weighted graphs. A vertex-failure distance oracle is a data structure that, given two vertices $x$ and $y$ and a failed vertex set $F$ of size at most $f$, returns an approximation to the distance between $x$ and $y$ in $G \setminus F$. In the labeling-scheme setting, the data structure needs to be stored distributively as labels on the vertices, and each query $(x,y,F)$ must be answered by accessing only the labels of the vertices in $F \cup \{x,y\}$. For any $f\geq 1$ and $k \ge 1$, we obtain a vertex-failure distance oracle with $O(k^{6})$ approximation, space $\tilde{O}(f^{2}n^{1+1/k})$, query time $\tilde{O}(f^{5}n^{1/k})$, and polynomial preprocessing time. In particular, this is the first time-efficient oracle for multiple vertex failures with space close to linear, as well as the first constant-approximation oracle with polynomial space when tolerating $Ω(\log n)$ vertex failures. The previous results, due to [Duan-Gu-Ren, SODA'21], gave two alternatives: for any constant $c \ge 1$ and $ε>0$, one oracle has $\mathrm{poly}(\log n,f)$ approximation, space $n^{2+1/c}\mathrm{poly}(\log n,f)$, and query time $\mathrm{poly}(\log n,f^{c})$, while the other has $(1+ε)$ approximation, space $n^{2+1/c}(\log n/ε)^{O(f)}$, and query time $\mathrm{poly}(\log n,f^{c},1/ε)$. We also obtain a vertex-failure distance labeling scheme with $O(k^{6})$ approximation and label size $f^{3}n^{1/k}\log^{O(k)} n$. This is the first nontrivial distance labeling scheme for vertex failures. Our techniques build on recent tools related to length-constrained vertex expanders and also introduce a new expander-based shortcut sparsification. The latter also leads to a deterministic vertex-failure connectivity labeling scheme of size $\tilde{O}(f^{2})$.