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 ∈ 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 n4) and query time dO(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 Ω(nd) 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.