Maintaining exact distances under multiple edge failures

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 ∈ 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(dn 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 Ω(n d ) space [Duan and Pettie, SODA'09]. Our distance oracle seems to require n Ω(d) time to preprocess; we leave it as an open question to improve this preprocessing time.

• Most of this work was done when Hanlin Ren was affiliated with Tsinghua University.