New Approximate Distance Oracles and Their Applications

Our main result for stretch $\ge 2$ establishes a three-way tradeoff among the key parameters of distance oracles: stretch, space, and query time. This new tradeoff improves upon previously known results for specific values of stretch, space, and query time. We prove the following:

An interesting tradeoff that follows from Theorem 1 is a better space/stretch tradeoff than the classical Thorup and Zwick [36] $(2k-1)$-stretch / $\tilde{O}(n^{1+1/k})$ space tradeoff, at a cost of a larger query time. Specifically, by setting $r=\frac{c}{k}$, we get a $(2k(1-2r)-1)$-stretch distance oracle that uses $\tilde{O}(m+n^{1+1/k})$ space, at the price of $\tilde{O}(\mu n^r)$ query time. By setting $c=1$ in Theorem 1, we improve upon a recent result of Dalirrooyfard, Jin, V. Williams, and Wein [22]. They presented a $(2k-2)$-stretch distance oracle that uses $\tilde{O}(m+n^{1+1/k})$ space and $\tilde{O}(\mu n^{1/k})$ query time.⁵⁵5We remark that even more recently, Chechik, Hoch, and Lifshitz [20] presented a $(2k-3)$-stretch $n$-PSP algorithm, however, they did not present a new distance oracle. We improve the stretch from $(2k-2)$ to $(2k-5)$ while using the same space and query time.

To obtain Theorem 1, we develop a new technique called the borderline vertices technique. Given $u,v\in V$, the borderline vertices ${\tau }_u$ and ${\tau }_v$ are two vertices on the shortest path between $u$ and $v$ that satisfy special properties that allow us to better exploit the structure of the Thorup and Zwick distance oracle. Using the borderline vertices technique, we also manage to achieve the following distance oracle, which improves upon the construction time of Theorem 1 at the cost of increasing the stretch.

Agarwal, Godfrey, and Har-Peled [9] considered also small stretches, and presented a $2$-stretch distance oracle that uses $\tilde{O}(m+n^{3/2})$ space and has $\tilde{O}(\mu n^{1/2})$ query time, that is constructed in $\tilde{O}(m{n}^{1/2})$ time, and a $3$-stretch distance oracle that uses $\tilde{O}(m+n^{4/3})$ space and has $\tilde{O}(\mu n^{1/3})$ query time, and is constructed in $\tilde{O}(m{n}^{2/3})$ time. These results suggest that the following general stretch/space/query time tradeoff may exist for every $k$.

Agarwal, Godfrey, and Har-Peled [9] solved Problem 1 for $k=2,3$. By setting $c=1$ in Theorem 2 and Theorem 1, respectively, we obtain a $4$-stretch distance oracle that uses $\tilde{O}(m+n^{5/4})$ space and has $\tilde{O}(\mu n^{1/4})$ query time, and a $5$-stretch distance oracle that uses $\tilde{O}(m+n^{6/5})$ space and has $\tilde{O}(\mu n^{1/5})$ query time. Thus, we solve Problem 1 for $k=4,5$.

In addition, using the borderline vertices technique we obtain $(2k-3)$-stretch distance oracle that uses $\tilde{O}(m+n^{1+1/k})$ space, has $\tilde{O}(\mu n^{1/k})$ query time, and is constructed in $\tilde{O}(m{n}^{1/k})$ time. For $k=3$ this improves the construction time of [9] for a $3$-stretch distance oracle from $\tilde{O}(m{n}^{2/3})$ to $\tilde{O}(m{n}^{1/3})$. Our results for weighted graphs are summarized in Table 2.

Next, we turn our focus to unweighted graphs. An estimation $\widehat{d}(u,v)$ of $d(u,v)$ is an $(\alpha ,\beta )$-approximation if $d(u,v)\le \widehat{d}(u,v)\le \alpha d(u,v)+\beta$. $(\alpha ,\beta )$-approximations were extensively studied in the context of distance oracles, graph spanners, and emulators. (For more details see for example [24, 37, 11, 17, 16, 30, 1, 2, 9, 7, 13]).

From the girth conjecture, it follows that in unweighted graphs, for every $(\alpha ,\beta )$-distance oracle that uses $\tilde{O}(n^{1+1/k})$ space, it must hold that $\alpha +\beta \ge 2k-1$. However, this inequality must hold only for adjacent vertices. For non-adjacent vertex pairs, we prove the following simple lower bound.

A spanner is a subgraph $H\subseteq G$ that approximates distances without supporting distance queries. Baswana, Kavitha, Mehlhorn, and Pettie [11] and Parter [30] presented a $k$-spanner for every $u,v\in V$ such that $d(u,v)=2$, and matched the lower bound of Theorem 3 for spanners. An interesting question is whether this lower bound can be matched by distance oracles with efficient distance queries as well. Thus, we formulate the following problem.

Agarwal, Godfrey, and Har-Peled [9] presented for unweighted graphs a $(2,1)$-approximation distance oracle that uses $\tilde{O}(n^{3/2})$ space, has $\tilde{O}(n^{1/2})$ query time, and is constructed in $\tilde{O}(m{n}^{1/2})$ time. They also presented a $(3,2)$-approximation distance oracle that uses $\tilde{O}(n^{4/3})$ space, has $\tilde{O}(n^{1/3})$ query time, that is constructed in $\tilde{O}(m{n}^{2/3})$ time.

By analyzing more carefully the $(2,1)$-approximation distance oracle of [9] it is possible to show that it is actually a $(2,1_{\text{odd}})$-approximation⁶⁶6$x_{\text{odd}}$ is defined as $x\cdot 1_{\text{odd}}$, where $1_{\text{odd}}$ is $d(u,v)mod2$ distance oracle, and therefore solves Problem 2 for $k=2$.⁷⁷7In their work, the additive error comes from the fact that if $B(u)\cap B(v)=\mathrm{\varnothing }$ then $\min (h(u),h(v))\le d(u,v)/2+1$. However, this can be improved by showing that if $B(u)\cap B(v)=\mathrm{\varnothing }$ then $\min (h(u),h(v))\le d(u,v)/2+1_{\text{odd}}$. In the following two theorems, we show that it is possible to solve Problem 2 for $k=3$ and $k=4$ as well.

In Theorem 4 we improve the distance oracle of [9] from more than a decade ago. In particular we improve the construction time from $\tilde{O}(m{n}^{2/3})$ to $\tilde{O}(m{n}^{1/3})$, and the approximation from $(3,2)$ to $(3,2_{\text{odd}})$. Dalirrooyfard, Jin, V. Williams, and Wein [22] presented a $(2k-2,2_{\text{odd}})$-stretch distance oracle that uses $\tilde{O}(n^{1+1/k})$ space and $\tilde{O}(n^{1/k})$ query time. By setting $k=4$ in the $(2k-2,2_{\text{odd}})$-stretch distance oracle of [22] they obtain a $(6,2_{\text{odd}})$-stretch distance oracle. In Theorem 5 we improve the approximation from $(6,2_{\text{odd}})$ to $(4,3_{\text{odd}})$ while maintaining the same space and query time.

To obtain our new distance oracles for unweighted graphs, presented in Theorem 4 and Theorem 5, we develop a new technique for using the middle vertex in the path, called the middle vertex technique. Let $u,v\in V$, the middle vertex $\tau$ is a vertex on the shortest path between $u$ and $v$ that satisfies $d(u,\tau )=d(u,v)/2+{0.5}_{\text{odd}}$ and $d(v,\tau )=d(u,v)/2-{0.5}_{\text{odd}}$. As with the borderline vertices technique for sparse weighted graphs, the middle vertex technique enables us to better exploit the structure of the distance oracles of Thorup and Zwick in dense unweighted graphs.

By combining the middle vertex technique with the borderline vertices technique, we manage to achieve two more distance oracles for dense unweighted graphs. The first distance oracle improves the approximation of the distance oracle of Theorem 5 from $(4,3_{\text{odd}})$ to $(3,2+2_{\text{odd}})$ at the cost of increasing the query time to $\tilde{O}(n^{1/2})$.

The second distance oracle improves the $(2k-2,2_{\text{odd}})$-approximation of [22] to $(2k-5,4+2_{\text{odd}})$-approximation, while using the same space and query time.

Our results for unweighted graphs are summarized in Table 1.

For distance oracles with stretch in weighted graphs, we present the following new three-way tradeoff between: stretch, space, and query time. We prove:

Using this tradeoff, we obtain the first distance oracle with stretch , sublinear query time, and $\tilde{O}(m+n^{1.5-\alpha })$ space, for $\alpha >0$. In particular, by setting $t=3$ and $c=1/3-\epsilon$, we obtain a $5/3$-stretch distance oracle with $\tilde{O}(m+n^{4/3+2\epsilon })$-space and $O({\mu }^3{n}^{1-3\epsilon })$-query time. For comparison, Agarwal [6] presented a distance oracle with stretch $1+\frac{1}{t+0.5}$, using $\tilde{O}(m+n^{2-c})$ space and $\tilde{O}({\mu }^t{n}^{(t+1)c})$ query time. Setting $t=1$ and $c=1/2-\epsilon$ in the construction of [6] yields a $5/3$-stretch oracle with $\tilde{O}(m+n^{1.5+\epsilon })$-space and $\tilde{O}(\mu n^{0.5-\epsilon })$-query time. (See Table 2.)

For unweighted graphs, we present two new tradeoffs. The first improves upon the tradeoff of the distance oracle of Bilò, Chechik, Choudhary, Cohen, Friedrich, and Schirneck [13], while preserving the same space and query time. Specifically, they presented a distance oracle for unweighted graphs that uses $\tilde{O}(n^{2-c})$ space, has $\tilde{O}(n^{tc})$ query time, and returns an estimate $\widehat{d}(u,v)\le (1+1/t)d(u,v)+2$. In the following theorem, we slightly improve the stretch bound to $\widehat{d}(u,v)\le d(u,v)+2\lceil \frac{d(u,v)}{2t}\rceil$, while using the same space and query time.

Next, by adapting methods of Theorem 8 to unweighted graphs, we obtain another tradeoff that uses less space than the tradeoff of Theorem 9 at the cost of a larger query time. We prove:

In particular, using Theorem 10 we obtain the first distance oracle with $o(n^{1.5-\alpha })$-space, for $\alpha >0$, that achieves a multiplicative error strictly better than $2$. Specifically, by setting $t=3$ and $c=1/3-\epsilon$, we get a distance oracle with $\tilde{O}(n^{4/3+2\epsilon })$ space and $\tilde{O}(n^{1-3\epsilon })$ query time. These results are summarized in Table 1.

Recently, Dalirrooyfard, Jin, V. Williams, and Wein [22] (followed by Chechik, Hoch and Lifshitz [20]) studied two fundamental problems in graphs, the $n$-pairs shortest paths ($n$-PSP) problem and the all-nodes shortest cycles ($ANSC$) problem. The $n$-PSP problem is defined as follows. Given a set of vertex pairs $(s_i,t_i)$, for $1\le i\le O(n)$, compute the distance $d(s_i,t_i)$. The $ANSC$ problem is defined as follows. Compute the length of the shortest simple cycle that contains $v$, for every $v\in V$.

A straightforward approach for solving the $n$-PSP problem is to first construct a distance oracle and then query it for every pair in the input set. The total runtime of this approach is the sum of the construction time and $n$ times the query time of the distance oracle. While this method naturally yields an $n$-PSP algorithm, a distance oracle must satisfy additional requirements that an $n$-PSP algorithm does not. In particular, a distance oracle must use limited space and support queries between any of the $\mathrm{\Omega }(n^2)$ pairs of vertices.

Using our new distance oracles, we obtain improved time/stretch tradeoffs for both the $n$-PSP problem and the $ANSC$-problem, improving some of the results of [22, 20].

In [22], a lower bound based on the combinatorial $4k$ clique hypothesis for the $n$-PSP problem is presented. They showed that $\mathrm{\Omega }(m^{2-\frac{2}{k+1}}\cdot n^{\frac{1}{k+1}-o(1)})$ time is required to achieve $(1+1/k-\epsilon )$ stretch. As mentioned in [22] using the $(1+1/k)$-distance oracle of [6] it is possible to solve $n$-PSP with $(1+1/k)$-stretch in $O(m^{2-\frac{2}{k+1}}{n}^{\frac{1}{k+1}})$ time, which almost matches the lower bound of [22]. In this paper, we show that it is possible to significantly improve the running time of [6] and to bypass the lower bound of [22] at the cost of a small additive error (of up to $2$). We obtain an $O(m^{1-\frac{1}{k+1}}n)$ time algorithm that returns $\widehat{d}(s_i,t_i)\le d(s_i,t_i)+2\lceil \frac{d(s_i,t_i)}{2k}\rceil \le (1+1/k)d(u,v)+2$, as presented in the following theorem.

In [22] they presented an $O(m+n^{2/k})$ time $n$-PSP algorithm that returns $(2k-2)(2k-1)$-stretch. In the following theorem we improve the stretch from $(2k-1)(2k-2)$ to $(2k-1)(2k-3)$ while using the same running time.

For the $ANSC$ problem, [22] presented an $O(m^{2-2/k}{n}^{1/k})$ running time algorithm that for every $u\in V$ returns estimate $\widehat{c}(u)$ such that ${\widehat{c}}_u\le SC(u)+2\lceil \frac{SC(u)}{2(k-1)}\rceil$, where $SC(u)$ is the length of the shortest simple cycle that contains $u$. In the following theorem, we improve the running time from $O(m^{2-2/k}{n}^{1/k})$ of [22] to $\tilde{O}(m{n}^{1-\frac{1}{k}})$.

In addition, we present the first, to the best of our knowledge, stretch algorithm for the $ANSC$ problem in weighted graphs. Specifically, we present an $O(m^{2-1/k})$ time algorithm for weighted graphs that for every $u\in V$ returns an estimate $\widehat{c}$ such that ${\widehat{c}}_u\le 1+\frac{1}{k-1}SC(u)$, as presented in the following theorem.

Our results for the $ANSC$ problem are summarized in Table 4.

The rest of this paper is organized as follows. In the next section, we present some necessary preliminaries. In Section 3 we present a technical overview of our main techniques and some of our new distance oracles. In the full version [27] of the paper, we present the full proofs of our techniques, distance oracles, applications, and lower bound.