New approximate distance oracles and their applications

Avi Kadria, Liam Roditty · 2025

Read New approximate distance oracles and their applications by Avi Kadria, Liam Roditty (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-00890.txt.

Introduction

Avi Kadria and one co-author, Liam Roditty, present new approximate distance oracles and their applications. A distance oracle is a data structure that answers approximate distance queries in a graph, balancing low stretch, the error factor, efficient space, and fast query time.

Prior work focused on constant query time. Kadria and Roditty comprehensively study oracles with non-constant query time, exploring trade-offs among space, stretch, and query time for weighted and unweighted graphs in stretch regimes below and above two. They give a new three-way trade-off extending the classical Thorup-Zwick oracle to larger query times, with explicit space and query bounds. Applications follow to the n-pairs shortest paths problem and the all nodes shortest cycles problem.

Catalog record

CREATORAvi Kadria, Liam Roditty
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE142 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-00890

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

New approximate distance oracles and their applications Avi Kadria, Liam Roditty Abstract Let G = ( V , E ) G=(V,E) be an undirected graph with n n vertices and m m edges, and let μ = m / n \mu=m/n . A distance oracle is a data structure designed to answer approximate distance queries, with the goal of achieving low stretch, efficient space usage, and fast query time. While much of the prior work focused on distance oracles with constant query time, this paper presents a comprehensive study of distance oracles with non-constant query time. We explore the tradeoffs between space, stretch, and query time of distance oracles in various regimes. Specifically, we consider both weighted and unweighted graphs in the regimes of stretch < 2 <2 and stretch ≥ 2 \geq 2 . In addition, we demonstrate several applications of our new distance oracles to the n n -Pairs Shortest Paths ( n n -PSP) problem and the All Nodes Shortest Cycles ( A ​ N ​ S ​ C ANSC ) problem. Our main contributions are: • Weighted graphs: We present a new three-way trade-off between stretch, space, and query time, offering a natural extension of the classical Thorup–Zwick distance oracle [STOC’01 and JACM’05] to regimes with larger query time. Specifically, for any 0 < r < 1 / 2 0<r<1/2 and integer k ≥ 1 k\geq 1 , we construct a ( 2 ​ k ​ ( 1 − 2 ​ r ) − 1 ) (2k(1-2r)-1) -stretch distance oracle with O ~ ​ ( m + n 1 + 1 / k ) \tilde{O}(m+n^{1+1/k}) space and O ~ ​ ( μ ​ n r ) \tilde{O}(\mu n^{r}) query time. This construction provides an asymptotic improvement over the classical ( 2 ​ k − 1 ) (2k-1) -stretch and O ⁡ ( n 1 + 1 / k ) O(n^{1+1/k}) -space tradeoff of Thorup and Zwick in sparse graphs, at the cost of increased query time. We also improve upon a result of Dalirrooyfard et al. [FOCS’22], who presented a ( 2 ​ k − 2 ) (2k-2) -stretch distance oracle with O ⁡ ( m + n 1 + 1 / k ) O(m+n^{1+1/k}) space and O ⁡ ( μ ​ n 1 / k ) O(\mu n^{1/k}) query time. In our oracle we reduce the stretch from ( 2 ​ k − 2 ) (2k-2) to ( 2 ​ k − 5 ) (2k-5) while preserving the same space and query time. • Unweighted graphs: We present a ( 2 ​ k − 5 , 4 + 2 odd ) (2k-5,4+2_{\textsc{odd}}) -approximation 1 1 1 2 odd = 2 ⋅ ( d ⁡ ( u , v ) mod 2 ) 2_{\textsc{odd}}=2\cdot(d(u,v)\mod 2) . distance oracle with O ⁡ ( n 1 + 1 / k ) O(n^{1+1/k}) space and O ⁡ ( n 1 / k ) O(n^{1/k}) query time. This improves upon a ( 2 ​ k − 2 , 2 odd ) (2k-2,2_{\textsc{odd}}) -approximation distance oracle of Dalirrooyfard et al. [FOCS’22] while maintaining the same space and query time. We also present a distance oracle that given u , v ∈ V u,v\in V returns an estimate d ^ ​ ( u , v ) ≤ d ⁡ ( u , v ) + 2 ​ ⌈ d ⁡ ( u , v ) / 3 ⌉ + 2 \hat{d}(u,v)\leq d(u,v)+2\lceil d(u,v)/3\rceil+2 , using O ⁡ ( n 4 / 3 + 2 ​ ε ) O(n^{4/3+2\varepsilon}) space and O ⁡ ( n 1 − 3 ​ ε ) O(n^{1-3\varepsilon}) query time. To the best of our knowledge, this is the first distance oracle that simultaneously achieves a multiplicative stretch < 2 <2 , and a space complexity O ⁡ ( n 1.5 − α ) O(n^{1.5-\alpha}) , for some α > 0 \alpha>0 . • Applications for n n -PSP and A ​ N ​ S ​ C ANSC : We present an O ~ ​ ( m 1 − 1 / ( k + 1 ) ​ n ) \tilde{O}(m^{1-1/(k+1)}n) -time algorithm for the n n -PSP problem, that for every input pair ⟨ s i , t i ⟩ \langle s_{i},t_{i}\rangle , where i ∈ [ n ] i\in[n] , returns an estimate d ^ ​ ( s i , t i ) \hat{d}(s_{i},t_{i}) such that d ^ ​ ( s i , t i ) ≤ d ⁡ ( s i , t i ) + 2 ​ ⌈ d ⁡ ( s i , t i ) / 2 ​ k ⌉ \hat{d}(s_{i},t_{i})\leq d(s_{i},t_{i})+2\lceil d(s_{i},t_{i})/2k\rceil . By allowing a small additive error, this result circumvents the conditional running time lower bound of Ω ⁡ ( m 2 − 2 k + 1 ⋅ n 1 k + 1 − o ⁡ ( 1 ) ) \Omega\left(m^{2-\frac{2}{k+1}}\cdot n^{\frac{1}{k+1}-o(1)}\right) , established by Dalirrooyfard et al. [FOCS’22] for achieving ( 1 + 1 / k ) (1+1/k) -stretch. Additionally, we present an O ~ ​ ( m ​ n 1 − 1 / k ) \tilde{O}(mn^{1-1/k}) -time algorithm for the A ​ N ​ S ​ C ANSC problem that computes, for every u ∈ V u\in V , an estimate c ^ u \hat{c}_{u} such that c ^ u ≤ S ​ C ​ ( u ) + 2 ​ ⌈ S ​ C ​ ( u ) / 2 ​ ( k − 1 ) ⌉ \hat{c}_{u}\leq SC(u)+2\lceil SC(u)/2(k-1)\rceil , where S ​ C ​ ( u ) SC(u) denotes the length of the shortest cycle containing u u . This improves upon the O ~ ​ ( m 2 − 2 / k ​ n 1 / k ) \tilde{O}(m^{2-2/k}n^{1/k}) -time algorithm of Dalirrooyfard et al. [FOCS’22], while achieving the same approximation guarantee. We obtain our results by developing several new techniques, among them are the borderline vertices technique and the middle vertex technique, which may be of independent interest. 1 Introduction Let G=(V,E) be an undirected graph with n=|V| vertices and m=|E| edges with non-negative real edge weights, and let \mu=m/n be the average degree. The distance d_{G}(u,v) between u and v is the length of the shortest path 2 2 2 We omit G when it is clear from the context. between u and v in G . An estimation \hat{d}(u,v) of d(u,v) is an \alpha -stretch if d(u,v)\leq\hat{d}(u,v)\leq\alpha\cdot d(u,v) . In their seminal work, Thorup and Zwick [ TZ05 ] presented a data structure for distance approximations called a distance oracle . A distance oracle is a data structure with o(n^{2}) space (otherwise we can trivially store the distance matrix), that supports distance queries between vertices. For any integer k\geq 1 , they [ TZ05 ] showed that in O(kmn^{1/k}) expected time, it is possible to preprocess a weighted undirected graph and create a distance oracle of size O(kn^{1+1/k}) . For every u,v\in V the query of the distance oracle returns a (2k-1) -stretch for d(u,v) in O(k) time. Different aspects of distance oracles, such as construction time, query time, and stretch, have been studied since their introduction, more than two decades ago. For more details see for example [ BK10 , MN06

Read the complete text