Path-Reporting Distance Oracles with Logarithmic Stretch and Size \({O}\)(\({n}\) \({\log \log }\) \({n}\))

Abstract. Given an [Formula: see text]-vertex undirected graph [Formula: see text], and a parameter [Formula: see text], a path-reporting distance oracle (PRDO) is a data structure of size [Formula: see text] that given a query [Formula: see text] returns an [Formula: see text]-approximate shortest [Formula: see text]-[Formula: see text] path [Formula: see text] in [Formula: see text] within time [Formula: see text]. Here [Formula: see text], [Formula: see text], and [Formula: see text] are arbitrary (hopefully slowly growing) functions. A distance oracle that only returns an approximate estimate [Formula: see text] of the distance [Formula: see text] between the queried vertices is called a non-path-reporting distance oracle. A landmark PRDO [M. Thorup and U. Zwick, Proceedings of the 33 rd ACM Symposium on Theory of Computing, 2001, pp. 183–192; C. Wulff-Nilsen, Proceedings of the 24 th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 539–549] has [Formula: see text], [Formula: see text], and [Formula: see text]. The size of this oracle is [Formula: see text] for all [Formula: see text]. PRDOs with [Formula: see text], [Formula: see text], and [Formula: see text], for [Formula: see text], were devised in [M. Elkin and S. Pettie, ACM Trans. Algorithms, 12 (2016), 50; O. Neiman and I. Shabat, 19 th Scandinavian Symposium and Workshops on Algorithm Theory, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2024, 36]. These oracles can be much sparser than [Formula: see text], but their stretch is polynomially larger than the optimal bound of [Formula: see text]. On the other hand, a long line of non-path-reporting distance oracles culminated in a celebrated result by Chechik [ Proceedings of the 47 th Annual ACM on Symposium on Theory of Computing, ACM, New York, 2015, pp. 1–10], in which [Formula: see text], [Formula: see text], and [Formula: see text]. In this paper we make dramatic progress in bridging the gap between path-reporting and non-path-reporting distance oracles. In particular, we devise a PRDO with size [Formula: see text], stretch [Formula: see text], and query time [Formula: see text]. As [Formula: see text] for [Formula: see text], its size is always at most [Formula: see text], and its query time is [Formula: see text]. Moreover, for [Formula: see text], we have [Formula: see text], i.e., [Formula: see text], [Formula: see text], and [Formula: see text]. For [Formula: see text], our oracle has size [Formula: see text], stretch [Formula: see text], and query time [Formula: see text]. These trade-offs exhibit polynomial improvement in stretch over the PRDOs of Elkin and Pettie and of Neiman and Shabat. For [Formula: see text], our trade-offs also strictly improve the long-standing bounds of Thorup and Zwick and of Wulff-Nilsen. Our results on PRDOs are based on novel constructions of approximate distance preservers, which we devise in this paper. Specifically, we show that for any [Formula: see text], any [Formula: see text], and any graph [Formula: see text] and a collection [Formula: see text] of [Formula: see text] vertex pairs, there exists a [Formula: see text]-approximate preserver for [Formula: see text] with [Formula: see text] edges, where [Formula: see text]. These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter [63 rd Annual Symposium on Foundations of Computer Science, IEEE, 2022, pp. 766–777].