Improved Distance (Sensitivity) Oracles with Subquadratic Space
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914917470175232 |
|---|---|
| author | Bilò, Davide Chechik, Shiri Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Schirneck, Martin |
| author_facet | Bilò, Davide Chechik, Shiri Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Schirneck, Martin |
| contents | A distance oracle (DO) with stretch $(α, β)$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$, returns a value $\widehat{d}(s,t)$ such that $d(s,t) \le \widehat{d}(s,t) \le α\cdot d(s,t) + β$. An $f$-edge fault-tolerant distance sensitivity oracle ($f$-DSO) additionally receives a set $F$ of up to $f$ edges and estimates the $s$-$t$-distance in $G{-}F$. Our first contribution is a new distance oracle with subquadratic space for undirected graphs. Introducing a small additive stretch $β> 0$ allows us to make the multiplicative stretch $α$ arbitrarily small. This sidesteps a known lower bound of $α\ge 3$ (for $β= 0$ and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0,W]$ that, for any positive integer $t$ and any $c \in (0, \ell/2]$, has stretch $(1{+}\frac{1}{\ell}, 2W)$, space $\widetilde{O}(n^{2-\frac{c}{t}})$, and query time $O(n^c)$. These are the first subquadratic-space DOs with $(1+ε, O(1))$-stretch generalizing Agarwal and Godfrey's results for sparse graphs [SODA 2013] to general undirected graphs. Our second contribution is a framework that turns a $(α,β)$-stretch DO for unweighted graphs into an $(α(1{+}\varepsilon),β)$-stretch $f$-DSO with sensitivity $f = o(\log(n)/\log\log n)$ and retains subquadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [STOC 2023, TheoretiCS 2024] for the special case of stretch $(3,0)$ and $f = O(1)$. By combining the framework with our new distance oracle, we obtain an $f$-DSO that, for any $γ\in (0, (\ell{+}1)/2]$, has stretch $((1{+}\frac{1}{\ell}) (1{+}\varepsilon), 2)$, space $n^{ 2- \fracγ{(\ell+1)(f+1)} + o(1)}/\varepsilon^{f+2}$, and query time $\widetilde{O}(n^γ /{\varepsilon}^2)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10014 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Distance (Sensitivity) Oracles with Subquadratic Space Bilò, Davide Chechik, Shiri Choudhary, Keerti Cohen, Sarel Friedrich, Tobias Schirneck, Martin Data Structures and Algorithms A distance oracle (DO) with stretch $(α, β)$ for a graph $G$ is a data structure that, when queried with vertices $s$ and $t$, returns a value $\widehat{d}(s,t)$ such that $d(s,t) \le \widehat{d}(s,t) \le α\cdot d(s,t) + β$. An $f$-edge fault-tolerant distance sensitivity oracle ($f$-DSO) additionally receives a set $F$ of up to $f$ edges and estimates the $s$-$t$-distance in $G{-}F$. Our first contribution is a new distance oracle with subquadratic space for undirected graphs. Introducing a small additive stretch $β> 0$ allows us to make the multiplicative stretch $α$ arbitrarily small. This sidesteps a known lower bound of $α\ge 3$ (for $β= 0$ and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in $[0,W]$ that, for any positive integer $t$ and any $c \in (0, \ell/2]$, has stretch $(1{+}\frac{1}{\ell}, 2W)$, space $\widetilde{O}(n^{2-\frac{c}{t}})$, and query time $O(n^c)$. These are the first subquadratic-space DOs with $(1+ε, O(1))$-stretch generalizing Agarwal and Godfrey's results for sparse graphs [SODA 2013] to general undirected graphs. Our second contribution is a framework that turns a $(α,β)$-stretch DO for unweighted graphs into an $(α(1{+}\varepsilon),β)$-stretch $f$-DSO with sensitivity $f = o(\log(n)/\log\log n)$ and retains subquadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [STOC 2023, TheoretiCS 2024] for the special case of stretch $(3,0)$ and $f = O(1)$. By combining the framework with our new distance oracle, we obtain an $f$-DSO that, for any $γ\in (0, (\ell{+}1)/2]$, has stretch $((1{+}\frac{1}{\ell}) (1{+}\varepsilon), 2)$, space $n^{ 2- \fracγ{(\ell+1)(f+1)} + o(1)}/\varepsilon^{f+2}$, and query time $\widetilde{O}(n^γ /{\varepsilon}^2)$. |
| title | Improved Distance (Sensitivity) Oracles with Subquadratic Space |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2408.10014 |