Algorithms and Complexity Seminar
Distance Oracles for Sparse Graphs
Christian Sommer (University of Tokyo)
Thorup and Zwick, in their seminal work, introduced the approximate
distance oracle, which is a data structure
that answers distance queries in a graph. For any integer k, they
showed an efficient algorithm to construct an approximate distance
oracle using space O(kn^{1+1/k}) that can answer queries in time O(k)
with a distance estimate that is at most 2k - 1 times larger than the
actual shortest distance (this ratio is called the stretch).
They proved that, under a combinatorial conjecture, their data
structure is optimal in terms of space: if a stretch of at most 2k-1
is desired, then the space complexity is at least n^{1+1/k}. Their
proof holds even if infinite query time is allowed: it is essentially
an "incompressibility" result. Also, the proof only holds for dense
graphs, and the best bound it can prove only implies that the size of
the data structure is lower bounded by the number of edges of the
graph. Naturally, the following question arises: what happens for
sparse graphs?
In this paper we give a new lower bound for approximate distance
oracles in the cell-probe model. This lower bound holds even for
sparse (polylog(n)-degree) graphs, and it is not an
"incompressibility" bound: we prove a three-way trade-off between
space, stretch, and query time. We show that when the query time is t
and the stretch is a, then the space S must be at least
n^{1+1/Omega(a t)} / lg n.
This lower bound follows by a reduction from lopsided set disjointness
to distance oracles, based on and motivated by recent work of
Patrascu. Our results in fact show that for any high-girth regular
graph, an approximate distance oracle that supports efficient queries
for all subgraphs of G must obey this trade-off. We also prove some
lemmas that count sets of paths in high-girth regular graphs and high-girth
regular expanders, which might be of independent interest.
Joint work with Elad Verbin and Wei Yu