Distance Oracles beyond the Thorup-Zwick Bound
Mihai Pǎtraşcu, Liam Roditty · 2010
We give the first improvement to the space/approximation trade-off of distance oracles since the seminal result of Thorup and Zwick [STOC'01]. For unweighted graphs, our distance oracle has size O(n5/3) = O(n1.66⋯) and, when queried about vertices at distance d, returns a path of length 2d + 1. For weighted graphs with m = n2/α edges, our distance oracle has size O(n2/3√α) and returns a factor 2 approximation. Based on a plausible conjecture about the hardness of set intersection queries, we show that a 2-approximate distance oracle requires space Ω̃(n2/√α). For unweighted graphs, this implies a Ω̃(n1.5) space lower bound to achieve approximation 2d + 1.