Nearly Optimal Fault Tolerant Distance Oracle

Abstract

We present an $f$-fault tolerant distance oracle for an undirected weighted graph where each edge has an integral weight from $[1\dots W]$. Given a set $F$ of $f$ edges, as well as a source node $s$ and a destination node $t$, our oracle returns the \emph{shortest path} from $s$ to $t$ avoiding $F$ in $O((cf\log (nW){)}^{O(f^2)})$ time, where $c>1$ is a constant. The space complexity of our oracle is $O(f^4{n}^2{\log }^2(nW))$. For a constant $f$, our oracle is nearly optimal both in terms of space and time (barring some logarithmic factor).

arXiv commentWe found the following error in the paper: in subcase (b) of case (III) of Section 9.3.1, we claimed that $s{e}_k=su\odot u{e}_k$, which is not correct in some cases. For example, when $x$ and $e_k$ lie on different branches of $T_s$, it may be that in $T_x$, the path from $x$ to $e_k$ uses a different path that goes through $u$. However, the technical claims about the Jump Sequence are correct