Approximate Distance Oracles with Improved Query Time

Abstract

Given an undirected graph $G$ with $m$ edges, $n$ vertices, and non-negative edge weights, and given an integer $k\ge 2$, we show that a $(2k-1)$-approximate distance oracle for $G$ of size $O(k{n}^{1+1/k})$ and with $O(\log k)$ query time can be constructed in $O(\min \{km{n}^{1/k},\sqrt{k}m+k{n}^{1+c/\sqrt{k}}\})$ time for some constant $c$. This improves the $O(k)$ query time of Thorup and Zwick. Furthermore, for any $0<\epsilon \le 1$, we give an oracle of size $O(k{n}^{1+1/k})$ that answers $((2+\epsilon )k)$-approximate distance queries in $O(1/\epsilon )$ time. At the cost of a $k$-factor in size, this improves the $128k$ approximation achieved by the constant query time oracle of Mendel and Naor and approaches the best possible tradeoff between size and stretch, implied by a widely believed girth conjecture of Erdős. We can match the $O(n^{1+1/k})$ size bound of Mendel and Naor for any constant $\epsilon >0$ and $k=O(\log n/\log \log n)$.

Minor additions and corrections. Added an extra figure. To appear at SODA 2013