Approximate Distance Queries in Sparse Graphs

Rachit Agarwal, P. Brighten Godfrey and Sariel Har-Peled

An approximate distance query data structure is a compact representation of a graph. It allows querying for approximate shortest paths between any pair of vertices in the graph. Thorup and Zwick proved that any approximate data structure that allows retrieval of stretch 2k-1 paths in constant time must require space Vmega(n^{1 + 1/k}). The hard cases that enforce their lower bound are, however, rather dense graphs with average degree Vmega(n^1/k).

We present data structures that, for sparse graphs, substantially break the Thorup-Zwick lower bound barrier, albeit at the expense of slightly higher query time. For instance, for the realistic scenario of a graph with n vertices and average degree \Theta( log n), the data structure of Thorup and Zwick requires O(n^3/2) space and constant query time for stretch 3 paths. Special cases of our data structures can retrieve stretch 2 paths with O(n^3/2) space and stretch 3 paths with O(n) space, albeit at the cost of O(\sqrt n) query time.

Postscript, PDF.

Last modified: Tue Jan 11 21:33:12 CST 2011