Approximate Single Source Dual Fault Tolerant Distance Oracle

Abstract

We are given an undirected weighted graph $G$ with $n$ vertices and $m$ edges, edge weights in $[1, W]$, and a designated source vertex $s$. We design a single source dual fault tolerant distance oracle for $G$. Given a destination vertex $t$ and a set $F$ of at most two faulty edges, the oracle returns a $(1 + O(ε))$-approximation of the weight of the shortest path from the source $s$ to $t$ avoiding $F$. Our oracle uses $\tilde{O}(n\sqrt{n})$ space and has $\tilde{O}(1)$ query time. Prior to our result, single source single fault tolerant oracles were known to return a $(1+ε)$ approximation of the weight of the shortest path using $\tilde{O}(n)$ space and $O(1)$ query time. However, extending these approaches to multiple faults remained an open problem. Indeed, all $(1+ε)$-approximate distance oracles that handle multiple faults require $Ω(n^2)$ space. We break this bound by presenting the first dual fault tolerant distance oracle with $o(n^2)$ space.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.