Path-Reporting Distance Oracles with Linear Size

Given an undirected weighted graph, an (approximate) distance oracle is a data structure that can (approximately) answer distance queries. A { Path-Reporting Distance Oracle}, or { PRDO}, is a distance oracle that must also return a path between the queried vertices. Given a graph on n vertices and an integer parameter k≥ 1, Thorup and Zwick {TZ01} showed a PRDO with stretch $2k-1$, size O(k· n1+1/k) and query time $O(k)$ (for the query time of PRDOs, we omit the time needed to report the path itself). Subsequent works {MN06,C14,C15} improved the size to O(n1+1/k) and the query time to $O(1)$. However, these improvements produce distance oracles which are not path-reporting. Several other works {ENW16,EP15} focused on small size PRDO for general graphs, but all known results on distance oracles with linear size suffer from polynomial stretch, polynomial query time, or not being path-reporting. In this paper we devise the first linear size PRDO with poly-logarithmic stretch and low query time O(loglog n). More generally, for any integer k≥ 1, we obtain a PRDO with stretch at most O(k4.82), size O(n1+1/k), and query time O(log k). In addition, we can make the size of our PRDO as small as $n+o(n)$, at the cost of increasing the query time to poly-logarithmic. For unweighted graphs, we improve the stretch to O(k²). We also consider { pairwise PRDO}, which is a PRDO that is only required to answer queries from a given set of pairs P. An exact PRDO of size O(n+| P|²) and constant query time was provided in {EP15}. In this work we dramatically improve the size, at the cost of slightly increasing the stretch. Specifically, given any ε>0, we devise a pairwise PRDO with stretch 1+ε, constant query time, and near optimal size nᵒ⁽¹⁾· (n+| P|).