Faster Algorithms for $(2k-1)$-Stretch Distance Oracles

In their seminal work¹¹1Winner of the 20-year Test-of-Time award of STOC 2021. on distance oracles, Thorup and Zwick [32] presented an algorithm that constructs in $O(km{n}^{\frac{1}{k}})$ expected²²2Later, Roditty, Thorup, and Zwick [31] derandomized the construction. time, for any integer $k\ge 1$, a $(2k-1)$-stretch distance oracle that uses $O(k{n}^{1+\frac{1}{k}})$ space and answers distance queries in $O(k)$ time. Many different aspects of distance oracles, including fast construction algorithms, have been studied since the introduction of distance oracles [29, 20, 22, 23, 18, 34, 9, 27, 28, 4, 3, 24, 17, 35].

Assuming the Erdős girth conjecture, the $(2k-1)$-stretch / $O(k{n}^{1+\frac{1}{k}})$-space tradeoff established in [32] is optimal. Chechik [15, 16] improved the $O(k)$ query time to $O(1)$. Therefore, the main open problem regarding distance oracles that remains is improving its construction time. In the words of Thorup and Zwick [32]:

“It remains an interesting open problem, however, to reduce the preprocessing times of small stretch oracles.”

Thorup and Zwick [32]

The $O(m{n}^{\frac{1}{k}})$ construction algorithm of Thorup and Zwick [32] is super-quadratic (in $n$) whenever $m=\omega (n^{2-\frac{1}{k}})$. Baswana and Kavitha [9] addressed this problem and presented an $O(n^2)$ construction-time algorithm, for every $k\ge 2$. In light of the quadratic time algorithm of Baswana and Kavitha [9], Wulff-Nilsen [34] considered the following problem.

Wulff-Nilsen [34] presented an $O(km+k{n}^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$ time construction algorithm, which is truly subquadratic time for every $k\ge 6$. Therefore, this resolves Problem 1 for all $k\ge 6$. Similar to Thorup and Zwick, Wulff-Nilsen suggested focusing on small stretch oracles and asked whether subquadratic time algorithms exist for smaller values of $k$.

In this paper, we provide an almost complete answer to Problem 1 by presenting a truly subquadratic-time construction algorithm for every $k>2$, leaving only the case that $k=2$ open⁴⁴4We highlight that solving 1 for $k=2$ and achieving a $3$-stretch distance oracle in truly subquadratic time – even without imposing space constraints – would be a significant breakthrough. Such a result would improve upon the long-standing $\tilde{O}(n^2)$-time $3$-stretch all-pairs shortest paths (APSP) algorithm of Cohen and Zwick [19], and would be a foundational advancement in the development of approximation algorithms for $APSP$.. We achieve a running time of $O(\max (n^{1+2/k},m^{1-\frac{1}{k-1}}{n}^{\frac{2}{k-1}})\log \log n)$, which for graphs with $m=O(n^{2-\epsilon })$, is truly subquadratic time of $O(n^{2-\epsilon (1-\frac{1}{k-1})})$. Moreover, this is the first improvement over the $O(m{n}^{1/k})$ construction time of Thorup and Zwick [32] in graphs with edges, for any $\epsilon >0$.

After breaking the quadratic time barrier for every $k>2$, we shift our focus to achieving optimal⁵⁵5$\mathrm{\Omega }(m)$ construction time is required due to a simple reduction to $(s,t)$-connectivity. linear construction time, as formalized in the following problem.

A running time of $\tilde{O}(m+n^{1+f(k)})$ is nearly linear for graphs where $m=\mathrm{\Omega }(n^{1+f(k)})$, and is therefore optimal (up to logarithmic factors) for such graphs. In other words, Problem 2 asks: what is the sparsest graph for which it is possible to construct a $(2k-1)$-stretch distance oracle with $\tilde{O}(1)$ query time and $\tilde{O}(n^{1+\frac{1}{k}})$ space in almost linear time?

There are two approaches to attack Problem 2. One approach is to prove a lower bound on the value of $f(k)$. Jin and Xu [25] proved that $\mathrm{\Omega }(m^{1+\frac{1}{2k-1}-o(1)})$ time is required for constructing a $(2k-1)$-stretch distance oracle, for graphs in which $m=\mathrm{\Theta }(n)$, conditioned on the $3$SUM conjecture. Independently, and also conditioned on the $3$SUM conjecture, Abboud, Bringmann, and Fischer [3] proved that $\mathrm{\Omega }(m^{1+\frac{1}{2k-1}-o(1)})$ time is required. These two results rule out linear-time construction for graphs with $m=\mathrm{\Theta }(n)$, which implies that $f(k)>0$.⁶⁶6Abboud, Bringmann, Khoury, and Zamir [4] previously proved that $\mathrm{\Omega }(m^{1+\frac{c}{k}-o(1)})$ construction time is required, for a small constant $c$.

In addition, Jin and Xu [25] proved that $\mathrm{\Omega }(m^{1+\frac{1}{4k-3}})$ time is required for constructing a $(2k-1)$-stretch distance oracle, for graphs in which $m=\mathrm{\Theta }(n^{1+\frac{1}{4k-4}})$, ruling out linear time construction for graphs with $m=\mathrm{\Theta }(n^{1+\frac{1}{4k-4}})$, and therefore showing that $f(k)>\frac{1}{4k-4}$, for every $k>1$.

Another approach to attack Problem 2 is to design a faster construction algorithm which improve the upper bound on $f(k)$. Wulff-Nilsen [34] presented two construction algorithms. The first algorithm with $O(km+k{n}^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$ running time was discussed above, and the second algorithm has $O(\sqrt{k}m+k{n}^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ running time. Combining these two algorithms with the $\tilde{O}(n^2)$-time algorithm of Baswana and Kavitha [9] we get:

In this paper, we improve the construction time of the Wulff-Nilsen [34] algorithms and present two new construction algorithms, as presented in the following two theorems.

Theorem 2 improves the $O(km+k{n}^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$ time of [34] and Theorem 3 improves the $O(\sqrt{k}m+k{n}^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ time of [34].

Combining these two algorithms, we significantly improve upon the current state of the art and obtain the following upper bound on $f(k)$:

In Table 1, we summarize our new construction algorithms for weighted undirected graphs and compare them to the previously known results. In Table 2 and Figure 2, we compare our new results on the sparsest graphs for which a linear-time construction algorithm exists with the prior work of [9, 34].

Our pursuit of faster construction algorithms leads us to develop several novel tools. Among them are new parameterized distance oracles. Parameterized distance oracles were first introduced by Roditty, Thorup, and Zwick [31]. Given a set $S\subseteq V$ as a parameter, they presented an $O(m{|S|}^{\frac{1}{k}})$-time construction algorithm that builds a $(2k-1)$-stretch distance oracle with $O(n{|S|}^{\frac{1}{k}})$ space, supporting queries only for vertex pairs $⟨s,v⟩\in S\times V$.

One of our new tools is a parameterized distance oracle, which is a natural generalization of the parameterized distance oracle of [31]. Our parameterized distance oracle is constructed in the same running time, uses the same amount of space. The oracle supports queries for every $⟨u,v⟩$ in $V\times V$, rather than in $S\times V$ as [31], at the cost of adding $2\min (h(u),h(v))$ to the estimate, where $h(x)$ is the distance from $x$ to $S$. Notice that if $u\in S$, then $h(u)=0$, and the stretch is $(2k-1)$ as in [31].

The main technical contribution of this paper is a new algorithmic tool called hierarchical distance oracles, which is composed of a hierarchy of parameterized distance oracles. This construction consists of $\log \log n$ such oracles, each built on a distinct subgraph of $G$ and parameterized by a different set $S$.

Using our new hierarchical distance oracle we obtain our $O(\max (n^{1+2/k},m^{1-\frac{1}{k-1}}{n}^{\frac{2}{k-1}}))$-time algorithm for constructing a $(2k-1)$-stretch distance oracle that uses $O(n^{1+\frac{1}{k}})$ space, mentioned above. We remark that this improves upon the $O(m{n}^{1/k})$-construction time of Thorup and Zwick [32], for graphs with $m=\mathrm{\Omega }(n^{1+\frac{1}{k}+\epsilon })$ edges.

In addition, we consider 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 graph spanners, emulators, and distance oracles. (For more details see for example [21, 33, 10, 14, 13, 30, 1, 2, 6, 5, 18, 12, 27, 7]).

Baswana, Gaur, Sen, and Upadhyay [8] considered estimations with an additive error, to obtain faster construction-time algorithms for distance oracles. They studied the following problem.

Baswana, Gaur, Sen and Upadhyay [8] presented an algorithm for constructing $(2k-1,2)$-approximation distance oracle that uses $O(k{n}^{1+\frac{1}{k}})$ space, for $k\ge 3$. The algorithm runs in $O(m+k{n}^{\frac{3}{2}+\frac{1}{k}+\frac{1}{k(2k-2)}})$ time. For $k=2$, they presented an algorithm that runs in $\tilde{O}(m+n^{23/12})$ time and constructs $(3,14)$-approximation distance oracle that uses $O(n^{1.5})$ space.

Combining these algorithms with the construction of Wulff-Nilsen [34] we get that the current state of the art for Problem 3 is:

In this paper, we improve the results of Baswana, Gaur, Sen, and Upadhyay [8] and present three new construction algorithms. The first construction algorithm runs in $\tilde{O}(km+k{n}^{\frac{3}{2}+\frac{1}{k-1}-\frac{1}{4k-6}})$ and constructs a $(2k-1,2)$-approximation distance oracle, improving the $\tilde{O}(m+k{n}^{\frac{3}{2}+\frac{1}{k}+\frac{1}{k(2k-2)}})$ construction time of [8], for every $k>2$. The second algorithm runs in $\tilde{O}(km+k{n}^{\frac{3}{2}+\frac{1}{2k}+\frac{3.5k-4.5}{k(4k^2-8k+3)}})$ time and constructs a $(2k-1,2k-2)$-approximation distance oracle. The third algorithm runs in $\tilde{O}(\sqrt{k}m+k{n}^{1+\frac{2}{\sqrt{k}}})$ time and constructs a $(2k-1,2k-1)$-approximation oracle. Combining these three algorithms, we significantly improve upon the current state of the art and obtain the following values for $f(k,\beta )$:

In addition, we present an $O(m{n}^{\epsilon }+n^{1+1/k+\epsilon })$ time algorithm for constructing a $((2k-1)(1+\epsilon ),\beta )$-distance oracle, improving the stretch of the $O(m+n^{1+1/k+\epsilon })$ time algorithm of [34] that constructs an $O(k)$-distance oracle.

The rest of this paper is organized as follows. In the next section, we present some necessary preliminaries. In Section 3, we overview our main results and techniques. In Section 4 we present our new tools, and specifically in Section 4.3 we present our new hierarchical distance oracle. In Section 5 we present our construction algorithms for weighted graphs, in the full version [26], we then present the new construction algorithms for unweighted graphs. For convenience, in Appendix A we include tables and graphs that summarize all the theorems.

Let $G=(V,E)$ be an undirected graph with $n=|V|$ vertices and $m=|E|$ edges. Throughout the paper, we consider unweighted and weighted graphs with non-negative real edge weights. Let $u,v\in V$, we denote $d_G(u,v)$ as the distance between $u$ and $v$ in $G$. Let $P(u,v)$ be the shortest path between $u$ and $v$. Let $N(u)\subseteq V$ be the neighbors of $u$ and let $deg(u)=|N(u)|$ be the degree of $u$.

Let $S\subseteq V$. The distance $d(u,S)$ between $u$ and $S$ is the distance between $u$ and the closest vertex to $u$ from $S$, that is, $d(u,S)={\min }_{s\in S}(d(u,s))$. We denote $d(u,S)$ with $h_S(u)$, and when $S$ is clear from the context, we write $h(u)$. Let $p_S(u)=\arg {\min }_{s\in S}(d(u,s))$ (ties are broken in favor of the vertex with a smaller identifier). Let . Let $E_S(v)$ be the set of edges incident to $v$ whose weight is at most $h_S(v)$, that is . Let $E_S={\bigcup }_{v\in V}{E}_S(v)$ and $G_S=(V,E_S)$. See Figure 1 for an illustration.

The following lemmas are standard results and are included here for completeness.

This section provides an overview of our construction algorithms and the key new tools we developed. To put our contribution in context, we begin by describing the framework underlying both construction algorithms of Wulff-Nilsen [34]. This framework consists of the following three steps:

1. (Step 1)

   Sample a set $S$ and create an oracle that upon a query on $u,v\in V$ produces ${\widehat{d}}_{G_S}(u,v)$.

2. (Step 2)

   Compute a spanner $H$.

3. (Step 3)

   Create an oracle that upon a query on $s_1,s_2\in S$ produces ${\widehat{d}}_H(s_1,s_2)$.

The distance oracle query of this framework returns $\min ({\widehat{d}}_{G_S}(u,v),h_S(u)+h_S(v)+{\widehat{d}}_H(p(u),p(v)))$. Using this framework, Wulff-Nilsen obtained an $O(\sqrt{k}m+k{n}^{1+\frac{2\sqrt{6}}{\sqrt{k}}+O(k^{-1})})$ construction-time algorithm as follows. In (Step 1) $\text{ADO}(G_S,k)$ is constructed. In (Step 2) a $(2k^{\prime }-1)$-spanner $H$ from Lemma 8 is computed. In (Step 3) $\text{ADO}(H,k^{\prime \prime })$ is constructed.

Next, we discuss the new main techniques that allow us to improve (Step 1). Notice that there is a tradeoff between $|S|$ and $|E_S|$. When $|E_S|$ is small, (Step 1) becomes faster and $|S|$ increases, resulting in a slower (Step 3). Given this tradeoff, the key to obtaining faster construction algorithms lies in the following optimization problem:

Thorup and Zwick’s [32] construction algorithm, which is used by Wulff-Nilsen for (Step 1), solves Problem 4 for graphs with $O(n^{1+x_0})$ edges. We improve the construction algorithm of [32], for every $x_0>\frac{1}{k}$ and solve Problem 4 for graphs with $O(n^{1+\frac{k-1}{k-2}{x}_0-\frac{1}{k(k-2)}})$ edges.

To obtain this improvement, we develop a new hierarchy of parameterized distance oracles, which we denote with hADO (see Theorem 18). The hierarchical distance oracle uses our new parameterized distance oracle, which we denote with ${\text{ADO}}_P$ (see Lemma 13).

To understand how hADO works, we first describe parametrized distance oracles. Let $S\subseteq V$. Roditty, Thorup, and Zwick [31] presented an $O(m{|S|}^{\frac{1}{k}})$-time construction algorithm for constructing a $(2k-1)$-stretch distance oracle that uses $O(n{|S|}^{\frac{1}{k}})$ space and supports queries for vertex pairs $⟨s,v⟩\in S\times V$. Our new parameterized distance oracle, ${\text{ADO}}_P$, is a generalization of the parameterized distance oracle of [31]. ${\text{ADO}}_P$ is constructed at the same time, uses the same space and query time, and supports queries for vertex pairs $⟨u,v⟩\in V\times V$ rather than $⟨s,v⟩\in S\times V$, and returns an estimate satisfying:

Notice that if $u\in S$ then $h_S(u)=0$ and ${\text{ADO}}_P(G,k,S)\text{.Query}(u,v)\le (2k-1)d(u,v)$, as in [31]. (For more details, see Section 4.2.)

The goal of the hADO is to compute distance oracles on denser graphs. To this end, we use a hierarchy of graphs that starts with sparse graphs and ends with denser graphs. Let $u,v\in V$ and let $G_{S_0}$, for some set $S_0$, be the first graph in the hierarchy. The main observation is that if we already know that $P(u,v)⊈G_{S_0}$ then, by Lemma 7, we have $h_{S_0}(u),h_{S_0}(v)\le d(u,v)$.

This allows us to consider the denser graph $G_{S_1}$, while maintaining the same stretch and running time by computing ${\text{ADO}}_P(G_{S_1},k-1,S_0)$. This solves the case in which $P(u,v)\subseteq G_{S_1}$. If $P(u,v)⊈G_{S_1}$ by Lemma 7 we have that $h_{S_1}(u),h_{S_1}(v)\le d(u,v)$ and we continue the process by computing ${\text{ADO}}_P(G_{S_2},k-1,S_1)$. We continue this process for $\log \log n$ levels, until two consecutive steps yield the same asymptotic density.

More formally, the hierarchical distance oracle hADO works as follows. Let $S_0$ be a set of size $n^{1-x_0}$, and construct $\text{ADO}(G_{S_0},k)$. Let $t=\lceil \log \log n\rceil$. For every $1\le i\le t$, construct ${\text{ADO}}_P(G_{S_i},k-1,S_{i-1})$, (roughly speaking, we use $k-1$ since the first level is the “$S$” set, this is required to get the desired stretch guarantee), where $S_i$ is a random set of size $n^{1-x_i}$ and $x_i=x_0-\frac{1}{k(k-1)}+\frac{x_{i-1}}{k-1}$.⁷⁷7Notice that $x_{i+1}-x_i=\frac{x_i-x_{i-1}}{k-1}\Rightarrow x_{i+1}>x_i$. Therefore and $|E_{S_{i+1}}|>|E_{S_i}|$. The query of hADO returns $\min (\text{ADO}(G_{S_0},k)\text{.Query}(u,v),{\min }_{1\le i\le t}({\text{ADO}}_P(G_{S_i},k-1,S_{i-1})\text{.Query}(u,v)))$.

The construction time of hADO is $\tilde{O}(n^{1+x_0+\frac{1}{k}})$. To see this notice that constructing ${\text{ADO}}_P(G_{S_i},k-1,S_{i-1})$ takes $O(|E_{S_i}|\times {|S_{i-1}|}^{\frac{1}{k-1}})=O(k{n}^{1+x_i+\frac{1-x_{i-1}}{k-1}})$ time, and since $x_i=x_0-\frac{1}{k(k-1)}+\frac{x_{i-1}}{k-1}$ we get $O(k{n}^{1+x_0-\frac{1}{k(k-1)}+\frac{x_{i-1}}{k-1}+\frac{1-x_{i-1}}{k-1}})=O(k{n}^{1+x_0+\frac{1}{k}})$.

For every $u,v$, where $P(u,v)\subseteq G_{S_t}$, we have that $\text{hADO}\text{.Query}(u,v)\le (2k-1)d(u,v)$. To see that, let $j$ be the first index for which $P(u,v)\subseteq G_{S_j}$. Since $P(u,v)⊈G_{S_{j-1}}$, it follows from Lemma 7 that $\max (h_{S_{j-1}}(u),h_{S_{j-1}}(v))\le d(u,v)$, thus, since ${\text{ADO}}_P$ was constructed with parameter $k-1$ we get ${\text{ADO}}_P(G_{S_j},k-1,S_{j-1})\text{.Query}(u,v)\le 2\min (h_{S_{j-1}}(u),h_{S_{j-1}}(v))+(2(k-1)-1)d(u,v)\le (2k-1)d(u,v)$. (See Lemma 17 for a complete proof.)

Our new hierarchical distance oracle, hADO, obtains a truly subquadratic construction algorithm for every $k\ge 3$, even without using the three-step framework presented above. Roughly speaking, the construction algorithm works as follows. Let $x_0$ be the solution for the equation $n^{1+\frac{k-1}{k-2}{x}_0-\frac{1}{k(k-2)}}=m$. One can verify that $x_0=\frac{({\log }_{n}m)(k^2-2k)-(k^2-2k-1)}{k(k-1)}$.

We construct $\text{hADO}(G,k,x_0)$. In the hierarchy, we have that $|E_{S_t}|=n^{1+\frac{k-1}{k-2}{x}_0-\frac{1}{k(k-2)}}=m$. Since $|E_{S_t}|=m$ we can replace $G_{S_t}$ with $G$ without affecting the construction time. Since $P(u,v)\subseteq G$ for every $u,v\in V$, we obtain a $(2k-1)$-stretch distance oracle. The construction time of this distance oracle is $\tilde{O}(n^{1+x_0+\frac{1}{k}})=\tilde{O}(m^{1-\frac{1}{k-1}}{n}^{\frac{2}{k-1}})$ (See Lemma 19). We remark that this is truly subquadratic since for $m=n^{2-\epsilon }$ we get a running time of $\tilde{O}(n^{(2-\epsilon )(1-\frac{1}{k-1})}{n}^{\frac{2}{k-1}})=\tilde{O}(n^{2-\epsilon (1-\frac{1}{k-1})})$, which is truly subquadratic for every $k>2$.

Next, we overview our improvement in the regime of linear construction-time algorithms. To improve the previous results, we use the framework described above and improve each step of the three-step framework as follows: In (Step 1) we use $\text{hADO}(G,k,x_0)$ as opposed to $\text{ADO}(G,k)$ as in [34]. This enables us to estimate distances in $G_{S_t}$ instead of $G_S$. In (Step 2) we compute a $(2k^{\prime }-1)$-spanner $H$ as in [34]. However, we augment $H$ with edges between $u$ and $p(u)$ of weight $h(u)$ for every $u\in V$. This enables us to bound $d_H(p(u),p(v))$ with $h(u)+h(v)+(2k^{\prime }-1)d(u,v)$ instead of $(2k^{\prime }-1)(h(u)+h(v)+d(u,v))$ as in [34].

For (Step 3) we develop an additional parameterized distance oracle, ${\text{ADO}}_{P^{\prime }}$ (see Lemma 14), that is constructed in $O(m{|S|}^{\frac{1}{k}})$ time, the same running time as ${\text{ADO}}_P$, but uses $O({|S|}^{1+\frac{1}{k}})$ space which is significantly less space than the $O(n{|S|}^{\frac{1}{k}})$ space required by ${\text{ADO}}_P$. The space reduction comes at a cost of supporting queries only for vertex pairs in $S\times S$. In (Step 3) we use ${\text{ADO}}_{P^{\prime }}(H,k-1,S_t)$ instead of $\text{ADO}(H,k)$ as in [34].

These improvements allows us to reduce the $O(\sqrt{k}m+k{n}^{1+\frac{2\sqrt{6}}{k}+O(k^{-1})})$ construction time of [34] to $O(\sqrt{k}m+k{n}^{1+\frac{2\sqrt{2}}{k}})$ and the $\tilde{O}(km+k{n}^{\frac{3}{2}+\frac{2}{k}+O(k^{-2})})$ construction time of [34] to $\tilde{O}(km+k{n}^{\frac{3}{2}+\frac{3}{4k-6}})$. (See Sections 5.3 and 5.2.)

By applying our new techniques to unweighted graphs and allowing a small additive error, we can further improve the construction time. In particular, among our results for unweighted graphs, we obtain a construction algorithm that in $O(km+k{n}^{\frac{3}{2}+\frac{0.75}{k}+O(k^{-2})})$ time constructs a $(2k-1,2)$-approximation distance oracle, improving the $O(km+k{n}^{\frac{3}{2}+\frac{1}{k}+O(k^{-2})})$ of Baswana, Gaur, Sen, and Upadhyay [8], for every $k>2$.

We remark that all of our construction algorithms can be de-randomized using the methods presented by Roditty, Thorup, and Zwick [31] at a logarithmic cost.

In this section, we develop our new techniques that we later use in our fast construction algorithms presented in Sections 5 and our new the unweighted construction algorithms in the full version [26]. We begin by proving several useful properties of the classical oracle of Thorup and Zwick [32] that are used by our parameterized distance oracles, presented right afterwards. The main new technical contribution, our new hierarchical distance oracle, is presented in the last part of this section, see Section 4.3.