Path-Reporting Distance Oracles for Vertex-Labeled Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914516388806656 |
|---|---|
| author | Neiman, Ofer Spector, Alon |
| author_facet | Neiman, Ofer Spector, Alon |
| contents | Let $G=(V,E)$ be a weighted undirected graph, with $n$ vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of \cite{TZ01}, given an integer $k\ge 1$, provides such an oracle with stretch $2k-1$, query time $O(k)$, and size $O(k\cdot n^{1+1/k})$. Furthermore, this oracle can also report a path in $G$ corresponding to the returned distance.
In this paper we focus on vertex-labeled graphs, in which each vertex is given a label from a set $L$ of size $\ell$. A {\em vertex-label distance oracle} answers queries of the form $(v,λ)$, where $v\in V$ and $λ\in L$, by reporting (an approximation to) the distance from $v$ to the closest vertex of label $λ$. Following \cite{HLWY11}, it was shown in \cite{C12} that for any integer $k> 1$, there exists a vertex-label distance oracle with stretch $4k-5$, query time $O(k)$, and size $O(k\cdot n\cdot \ell^{1/k})$.
This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in \cite{TZ01}, and it is not path-reporting. We address these concerns in this work, and provide the following results:
First, we devise a {\em path-reporting} vertex-label distance oracle, at the cost of a slight increase in stretch and size. For any constant $0<ε<1$, our oracle has stretch $(4k-5)\cdot(1+ε)$, query time $O(k)$, and size $O(n^{1+o(1)}\cdot \ell^{1/k})$.
Second, we show how to improve the stretch to the optimal $2k-1$, at the cost of mildly increasing the query time. Specifically, we devise a vertex-label distance oracle with stretch $2k-1$, query time $O(\ell^{1/k}\cdot\log n)$, and size $O(k\cdot n\cdot \ell^{1/k})$. \end{itemize} |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_26451 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Path-Reporting Distance Oracles for Vertex-Labeled Graphs Neiman, Ofer Spector, Alon Data Structures and Algorithms Let $G=(V,E)$ be a weighted undirected graph, with $n$ vertices. A distance oracle is a data structure that can quickly answer distance queries, with some stretch factor. A seminal work of \cite{TZ01}, given an integer $k\ge 1$, provides such an oracle with stretch $2k-1$, query time $O(k)$, and size $O(k\cdot n^{1+1/k})$. Furthermore, this oracle can also report a path in $G$ corresponding to the returned distance. In this paper we focus on vertex-labeled graphs, in which each vertex is given a label from a set $L$ of size $\ell$. A {\em vertex-label distance oracle} answers queries of the form $(v,λ)$, where $v\in V$ and $λ\in L$, by reporting (an approximation to) the distance from $v$ to the closest vertex of label $λ$. Following \cite{HLWY11}, it was shown in \cite{C12} that for any integer $k> 1$, there exists a vertex-label distance oracle with stretch $4k-5$, query time $O(k)$, and size $O(k\cdot n\cdot \ell^{1/k})$. This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in \cite{TZ01}, and it is not path-reporting. We address these concerns in this work, and provide the following results: First, we devise a {\em path-reporting} vertex-label distance oracle, at the cost of a slight increase in stretch and size. For any constant $0<ε<1$, our oracle has stretch $(4k-5)\cdot(1+ε)$, query time $O(k)$, and size $O(n^{1+o(1)}\cdot \ell^{1/k})$. Second, we show how to improve the stretch to the optimal $2k-1$, at the cost of mildly increasing the query time. Specifically, we devise a vertex-label distance oracle with stretch $2k-1$, query time $O(\ell^{1/k}\cdot\log n)$, and size $O(k\cdot n\cdot \ell^{1/k})$. \end{itemize} |
| title | Path-Reporting Distance Oracles for Vertex-Labeled Graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2604.26451 |