Michael Elkin

Given an n-vertex undirected graph G=(V,E,w), and a parameter k≥ 1, a path-reporting distance oracle (PRDO) is a data structure of size S(n,k) that given a query (u,v)∈ V² returns an f(k)-approximate shortest u-v path P in G within time q(k)+O(|P|). Here S(n,k), f(k), and q(k) are arbitrary (hopefully slowly growing) functions. A distance oracle that only returns an approximate estimate d̃(u,v) of the distance d_G(u,v) between the queried vertices is called a non-path-reporting distance oracle. A landmark PRDO [x14, x11, x15, Proceedings of the 33rd ACM Symposium on Theory of Computing, 2001, pp. 183–192; C. Wulff-Nilsen, Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, 2013, pp. 539–549] has (Formula presented), (Formula presented), and (Formula presented). The size of this oracle is Ω(nlog n) for all k. PRDOs with (Formula presented), and (Formula presented), for (Formula presented), were devised in [x14, Elkin and S. Pettie, ACM Trans. Algorithms, 12 (2016), 50; O. Neiman and I. Shabat, 19th 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 O(nlog n), but their stretch is polynomially larger than the optimal bound of 2k-1. On the other hand, a long line of non-path-reporting distance oracles culminated in a celebrated result by Chechik [Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, ACM, New York, 2015, pp. 1–10], in which (Formula presented), (Formula presented), and (Formula presented). 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 presented) (Formula presented), and query time q(k)(Formula presented), its size is always at most (Formula presented), and its query time is O(loglog k). Moreover, for (Formula presented), we have (Formula presented), i.e.,(Formula presented), (Formula presented). For (Formula presented), our oracle has size O(nloglog n), stretch O(log n), and query time O(log^(3)n). These trade-offs exhibit polynomial improvement in stretch over the PRDOs of Elkin and Pettie and of Neiman and Shabat. For (Formula presented), 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 ε>0, any k=1,2,…, and any graph G=(V,E,w) and a collection P of p vertex pairs, there exists a (1+ε)-approximate preserver for G,P with (Formula presented) edges, where (Formula presented). These new preservers are significantly sparser than the previous state-of-the-art approximate preservers due to Kogan and Parter [63rd Annual Symposium on Foundations of Computer Science, IEEE, 2022, pp. 766–777].