עופר נימן

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 [16], 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 [9], it was shown in [2] 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 [16], 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).