Path-Reporting Distance Oracles for Vertex-Labeled Graphs

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 Thorup and Zwick, 2005, given an integer k ≥ 1, provides such an oracle with stretch 2k-1, query time O (k), and size O (k⋅ 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 𝓁. A vertex-label distance oracle answers queries of the form (v, λ), where v ∈ V and λ ∈ L, by reporting (an approximation to) the distance from v to the closest vertex of label λ. Following Danny Hermelin et al. , 2011, it was shown in Chechik, 2012 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⋅ n⋅ 𝓁^1/k). This state-of-the-art result suffers from two main drawbacks: The stretch is roughly a factor of 2 larger than in Thorup and Zwick, 2005, and it is not path-reporting. We address these concerns in this work, and provide the following results. - First, we devise a 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) ⋅ (1+ε), query time O (k), and size O (n^1+o (1) ⋅ 𝓁^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 (𝓁^1/k⋅log n), and size O (k⋅ n⋅ 𝓁^1/k).