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 n^1+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 (n^1+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 (n). More generally, for any integer k 1, we obtain a PRDO with stretch at most O (k^4. 82), size O (n^1+1/k), and query time O (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^o (1) (n+| P|).