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 ( 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 Ω( 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.

Authors

• Ran Duan
• Hanlin Ren

Keywords

• distance sensitivity oracles
• dynamic data structures
• shortest paths