Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914922984636416 |
|---|---|
| author | Elkin, Michael Shabat, Idan |
| author_facet | Elkin, Michael Shabat, Idan |
| contents | Given an $n$-vertex undirected graph $G=(V,E,w)$, and a parameter $k\geq1$, a path-reporting distance oracle (or PRDO) is a data structure of size $S(n,k)$, that given a query $(u,v)\in V^2$, returns an $f(k)$-approximate shortest $u-v$ path $P$ in $G$ within time $q(k)+O(|P|)$. Here $S(n,k)$, $f(k)$ and $q(k)$ are arbitrary functions.
A landmark PRDO due to Thorup and Zwick, with an improvement of Wulff-Nilsen, has $S(n,k)=O(k\cdot n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(\log k)$. The size of this oracle is $Ω(n\log n)$ for all $k$. Elkin and Pettie and Neiman and Shabat devised much sparser PRDOs, but their stretch was polynomially larger than the optimal $2k-1$. On the other hand, for non-path-reporting distance oracles, Chechik devised a result with $S(n,k)=O(n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(1)$.
In this paper we make a dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. We devise a PRDO with size $S(n,k)=O(\lceil\frac{k\log\log n}{\log n}\rceil\cdot n^{1+\frac{1}{k}})$, stretch $f(k)=O(k)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$. We can also have size $O(n^{1+\frac{1}{k}})$, stretch $O(k\cdot\lceil\frac{k\log\log n}{\log n}\rceil)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$.
Our results on PRDOs are based on novel constructions of approximate distance preservers, that we devise in this paper. Specifically, we show that for any $ε>0$, any $k=1,2,...$, and any graph $G$ and a collection $\mathcal{P}$ of $p$ vertex pairs, there exists a $(1+ε)$-approximate preserver with $O(γ(ε,k)\cdot p+n\log k+n^{1+\frac{1}{k}})$ edges, where $γ(ε,k)=(\frac{\log k}ε)^{O(\log k)}$. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_04445 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n) Elkin, Michael Shabat, Idan Data Structures and Algorithms Given an $n$-vertex undirected graph $G=(V,E,w)$, and a parameter $k\geq1$, a path-reporting distance oracle (or PRDO) is a data structure of size $S(n,k)$, that given a query $(u,v)\in V^2$, returns an $f(k)$-approximate shortest $u-v$ path $P$ in $G$ within time $q(k)+O(|P|)$. Here $S(n,k)$, $f(k)$ and $q(k)$ are arbitrary functions. A landmark PRDO due to Thorup and Zwick, with an improvement of Wulff-Nilsen, has $S(n,k)=O(k\cdot n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(\log k)$. The size of this oracle is $Ω(n\log n)$ for all $k$. Elkin and Pettie and Neiman and Shabat devised much sparser PRDOs, but their stretch was polynomially larger than the optimal $2k-1$. On the other hand, for non-path-reporting distance oracles, Chechik devised a result with $S(n,k)=O(n^{1+\frac{1}{k}})$, $f(k)=2k-1$ and $q(k)=O(1)$. In this paper we make a dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. We devise a PRDO with size $S(n,k)=O(\lceil\frac{k\log\log n}{\log n}\rceil\cdot n^{1+\frac{1}{k}})$, stretch $f(k)=O(k)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$. We can also have size $O(n^{1+\frac{1}{k}})$, stretch $O(k\cdot\lceil\frac{k\log\log n}{\log n}\rceil)$ and query time $q(k)=O(\log\lceil\frac{k\log\log n}{\log n}\rceil)$. Our results on PRDOs are based on novel constructions of approximate distance preservers, that we devise in this paper. Specifically, we show that for any $ε>0$, any $k=1,2,...$, and any graph $G$ and a collection $\mathcal{P}$ of $p$ vertex pairs, there exists a $(1+ε)$-approximate preserver with $O(γ(ε,k)\cdot p+n\log k+n^{1+\frac{1}{k}})$ edges, where $γ(ε,k)=(\frac{\log k}ε)^{O(\log k)}$. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter. |
| title | Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n) |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2304.04445 |