Distance Oracles beyond the Thorup-Zwick Bound

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(n^5/3) = O(n^1.66⋯) and, when queried about vertices at distance d, returns a path of length 2d + 1. For weighted graphs with m = n²/α edges, our distance oracle has size O(n²/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 Ω̃(n²/√α). For unweighted graphs, this implies a Ω̃(n^1.5) space lower bound to achieve approximation 2d + 1.

I. Introduction

A distance oracle is a replacement for the all-pairs shortest paths matrix of a graph. Given a graph with vertices and edges, the goal is to construct a data structure of small (subquadratic) space, such that the distance between any two vertices can be computed efficiently (say, in constant time). Since subquadratic space is believed to be unattainable in the exact case, we allow approximation. Say the query asks about the distance between vertices and , and let . Then, a -approximate distance oracle might return a distance of . The oracle should also be able to list a path of length in constant time per hop.