Path-Reporting Distance Oracles for Vertex-Labeled Graphs
Pith reviewed 2026-05-07 11:49 UTC · model grok-4.3
The pith
Vertex-labeled graphs admit path-reporting distance oracles with stretch (4k-5)(1+ε) and size O(n^{1+o(1)} ℓ^{1/k}).
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We devise a path-reporting vertex-label distance oracle with stretch (4k-5)(1+ε), query time O(k), and size O(n^{1+o(1)} ℓ^{1/k}); and a vertex-label distance oracle with stretch 2k-1, query time O(ℓ^{1/k} log n), and size O(k n ℓ^{1/k}). Both are obtained by extending existing oracles for standard graphs and for vertex-labeled graphs while preserving their stretch and size bounds.
What carries the argument
Extension of prior distance oracles to the vertex-labeled setting that supports path reporting and reduces stretch to 2k-1 without introducing additional factors that depend on the total number of labels beyond the explicit ℓ^{1/k} terms.
If this is right
- Queries for approximate distance to the nearest vertex of a given label can be answered together with an explicit path in the graph.
- The stretch can be reduced from roughly twice the optimal to exactly the optimal factor 2k-1 by allowing the query time to grow with a sublinear power of the label-set size.
- The size remains polynomial in n and sublinear in the label-set size for any fixed k.
- No additional dependence on the label-set size appears beyond the explicit factors already present in the size and query bounds.
Where Pith is reading between the lines
- The same extension technique may apply to other labeled-graph problems such as nearest labeled neighbor search in geometric settings.
- In applications where labels represent categories, these oracles would enable efficient retrieval of both distance and route to the nearest instance of a category.
- The constructions close most of the gap between labeled and unlabeled distance oracles, leaving only a small constant stretch overhead or a mild query-time overhead.
Load-bearing premise
Prior distance oracles can be extended to handle label-based queries and to output paths while preserving the original stretch, query time, and size guarantees.
What would settle it
A family of vertex-labeled graphs on which every data structure with size O(n^{1+o(1)} ℓ^{1/k}) and query time O(k) must return distances with stretch strictly larger than (4k-5)(1+ε) on some query.
read the original abstract
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,\lambda)$, where $v\in V$ and $\lambda\in L$, by reporting (an approximation to) the distance from $v$ to the closest vertex of label $\lambda$. 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<\epsilon<1$, our oracle has stretch $(4k-5)\cdot(1+\epsilon)$, 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}
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents two constructions for vertex-label distance oracles in weighted undirected graphs with n vertices and ℓ labels. The first is a path-reporting oracle with stretch (4k-5)(1+ε) for constant ε>0, query time O(k), and size O(n^{1+o(1)} ℓ^{1/k}). The second achieves stretch 2k-1 with query time O(ℓ^{1/k} log n) and size O(k n ℓ^{1/k}). Both are obtained by extending the oracles of Thorup-Zwick (TZ01) and Cohen (C12), respectively, while adding path reporting in the first case.
Significance. If the extensions preserve the stated stretch, query, and size bounds without hidden ℓ-dependencies, the results close two gaps relative to the non-labeled case: they supply the first path-reporting vertex-label oracle and recover the optimal 2k-1 stretch. These improvements are directly useful for applications that require both approximate distances and explicit paths in labeled graphs, and the constructions inherit the parameter-free character of the base oracles with respect to k and ε.
minor comments (2)
- The size bound O(n^{1+o(1)} ℓ^{1/k}) for the path-reporting oracle hides the precise dependence of the o(1) term on ε; the main text should state this dependence explicitly (e.g., in terms of the sampling probabilities or the number of levels) so that the bound can be compared directly with the O(k n ℓ^{1/k}) bound of the second oracle.
- The abstract states that the second oracle improves stretch to 2k-1 'at the cost of mildly increasing the query time.' The main body should include a short comparison table or paragraph quantifying the query-time increase relative to the O(k) query time of C12, including any logarithmic factors introduced by the path-reporting mechanism or the label-set handling.
Simulated Author's Rebuttal
We thank the referee for the careful reading and positive assessment of the manuscript, including the recommendation for minor revision. The work extends the Thorup-Zwick and Cohen oracles to the vertex-labeled setting while preserving the claimed parameters (including path reporting in the first result).
Circularity Check
No significant circularity; derivations extend independent prior oracles
full rationale
The paper's central constructions are obtained by extending the independent results of TZ01 (Thorup-Zwick distance oracles) and C12 (vertex-label oracles), preserving their stretch/size bounds while adding path reporting. No equations, fitted parameters, or self-citations reduce the claimed bounds (stretch (4k-5)(1+ε) or 2k-1, sizes O(n^{1+o(1)} ℓ^{1/k}) and O(k n ℓ^{1/k})) to inputs of the present work by construction. The abstract and claims treat TZ01 and C12 as external black boxes whose properties are invoked without re-deriving them internally. No self-definitional loops, fitted-input predictions, uniqueness theorems imported from the authors, or ansatzes smuggled via self-citation appear in the provided material. This is the normal case of a self-contained algorithmic extension.
Axiom & Free-Parameter Ledger
free parameters (2)
- k
- ε
axioms (2)
- domain assumption G is an undirected weighted graph on n vertices.
- domain assumption The stretch and size bounds of TZ01 and C12 hold.
Reference graph
Works this paper leans on
-
[1]
Improved distance oracles and spanners for vertex-labeled graphs
[Che12] Shiri Chechik. Improved distance oracles and spanners for vertex-labeled graphs. In Algorithms–ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12,
work page 2012
-
[2]
Approximate distance oracles with improved bounds
13 [Che15] Shiri Chechik. Approximate distance oracles with improved bounds. In Rocco A. Servedio and Ronitt Rubinfeld, editors,Proceedings of the F orty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 1–10. ACM,
work page 2015
-
[3]
Path-reporting distance oracles with logarithmic stretch and linear size
[CZ24] Shiri Chechik and Tianyi Zhang. Path-reporting distance oracles with logarithmic stretch and linear size. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, July 8-12, 2024, Tallinn, Estonia, volume 297 ofLIPIcs, pages 42:1–42:18. Schloss Da...
work page 2024
-
[4]
Near-optimal distance oracles for vertex-labeled planar graphs
[EFW21] Jacob Evald, Viktor Fredslund-Hansen, and Christian Wulff-Nilsen. Near-optimal distance oracles for vertex-labeled planar graphs. In Hee-Kap Ahn and Kunihiko Sadakane, editors, 32nd International Symposium on Algorithms and Computation, ISAAC 2021, December 6-8, 2021, Fukuoka, Japan, volume 212 ofLIPIcs, pages 23:1–23:14. Schloss Dagstuhl - Leibni...
work page 2021
-
[5]
Path-reporting distance oracles with logarithmic stretch and size o(n log log n)
[ES23] Michael Elkin and Idan Shabat. Path-reporting distance oracles with logarithmic stretch and size o(n log log n). In64th IEEE Annual Symposium on F oundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 2278–2311. IEEE,
work page 2023
-
[6]
[HK25] Noam Horowicz and Tsvi Kopelowitz. Color distance oracles and snippets: Separation between exact and approximate solutions.CoRR, abs/2507.04578,
-
[7]
Distance oracles for vertex- labeled graphs
[HLWY11] Danny Hermelin, Avivit Levy, Oren Weimann, and Raphael Yuster. Distance oracles for vertex- labeled graphs. In Luca Aceto, Monika Henzinger, and Jir´ı Sgall, editors,Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part II, volume 6756 ofLecture Notes in Computer Sc...
work page 2011
-
[8]
Color-distance oracles and snippets
[KK16] Tsvi Kopelowitz and Robert Krauthgamer. Color-distance oracles and snippets. In Roberto Grossi and Moshe Lewenstein, editors,27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016, June 27-29, 2016, Tel Aviv, Israel, volume 54 ofLIPIcs, pages 24:1– 24:10. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik,
work page 2016
-
[9]
(1 +ϵ)-distance oracles for vertex-labeled planar graphs
[LMN13] Mingfei Li, Chu Chung Christopher Ma, and Li Ning. (1 +ϵ)-distance oracles for vertex-labeled planar graphs. In T.-H. Hubert Chan, Lap Chi Lau, and Luca Trevisan, editors,Theory and Ap- plications of Models of Computation, 10th International Conference, TAMC 2013, Hong Kong, China, May 20-22,
work page 2013
-
[10]
Optimal approximate distance oracle for planar graphs
[LW21] Hung Le and Christian Wulff-Nilsen. Optimal approximate distance oracle for planar graphs. In62nd IEEE Annual Symposium on F oundations of Computer Science, FOCS 2021, Denver , CO, USA, February 7-10, 2022, pages 363–374. IEEE,
work page 2021
-
[11]
On the size overhead of pairwise spanners
14 [NS24] Ofer Neiman and Idan Shabat. On the size overhead of pairwise spanners. In Venkatesan Guruswami, editor,15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA, volume 287 ofLIPIcs, pages 83:1–83:22. Schloss Dagstuhl - Leibniz-Zentrum f¨ur Informatik,
work page 2024
-
[12]
Approximate distance oracles with improved query time
[Wul13] Christian Wulff-Nilsen. Approximate distance oracles with improved query time. In Sanjeev Khanna, editor,Proceedings of the Twenty-F ourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 539–549. SIAM,
work page 2013
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.