Approximate distance oracles for unweighted graphs in expected <i>O</i> ( <i>n</i> ² ) time

Abstract

Let G = ( V , E ) be an undirected graph on n vertices, and let δ( u , v ) denote the distance in G between two vertices u and v . Thorup and Zwick showed that for any positive integer t , the graph G can be preprocessed to build a data structure that can efficiently report t -approximate distance between any pair of vertices. That is, for any u , v ∈ V , the distance reported is at least δ( u , v ) and at most t δ( u , v ). The remarkable feature of this data structure is that, for t ≥3, it occupies subquadratic space, that is, it does not store all-pairs distances explicitly, and still it can answer any t -approximate distance query in constant time. They named the data structure “approximate distance oracle” because of this feature. Furthermore, the trade-off between the stretch t and the size of the data structure is essentially optimal.In this article, we show that we can actually construct approximate distance oracles in expected O ( n 2 ) time if the graph is unweighted. One of the new ideas used in the improved algorithm also leads to the first expected linear-time algorithm for computing an optimal size (2, 1)-spanner of an unweighted graph. A (2, 1) spanner of an undirected unweighted graph G = ( V , E ) is a subgraph ( V , Ê), Ê ⊆ E , such that for any two vertices u and v in the graph, their distance in the subgraph is at most 2δ( u , v ) + 1.