Maintaining Exact Distances under Multiple Edge Failures

Abstract

We present the first compact distance oracle that tolerates multiple failures and maintains exact distances. Given an undirected weighted graph $G=(V,E)$ and an arbitrarily large constant $d$, we construct an oracle that given vertices $u,v\in V$ and a set of $d$ edge failures $D$, outputs the exact distance between $u$ and $v$ in $G-D$ (that is, $G$ with edges in $D$ removed). Our oracle has space complexity $O(d{n}^4)$ and query time $d^{O(d)}$. Previously, there were compact approximate distance oracles under multiple failures [Chechik, Cohen, Fiat, and Kaplan, SODA'17; Duan, Gu, and Ren, SODA'21], but the best exact distance oracles under $d$ failures require essentially $\Omega (n^d)$ space [Duan and Pettie, SODA'09]. Our distance oracle seems to require $n^{\Omega (d)}$ time to preprocess; we leave it as an open question to improve this preprocessing time.