Path-Reporting Distance Oracles with Logarithmic Stretch and Size \({O}\)(\({n}\) \({\log \log }\) \({n}\))
SIAM Journal on Computing · 31.12.2026 · 55 (6) · 1229-1292
DOI: 10.1137/24m1708954 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 02.11.2026. Verfasst von Michael Elkin und 1 weiteren Autor:innen. Die Arbeit nennt 72 Literaturangaben. Gefördert von: ISF.
Abstract (Originalsprache)
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].
Förderung
- ISF
Zitieren
APA
Elkin, M., & Shabat, I. (2026). Path-Reporting Distance Oracles with Logarithmic Stretch and Size \({O}\)(\({n}\) \({\log \log }\) \({n}\)). SIAM Journal on Computing, 55(6), 1229-1292. https://doi.org/10.1137/24m1708954
Vancouver
Elkin M, Shabat I. Path-Reporting Distance Oracles with Logarithmic Stretch and Size \({O}\)(\({n}\) \({\log \log }\) \({n}\)). SIAM Journal on Computing. 2026;55(6):1229-1292. doi:10.1137/24m1708954
BibTeX
@article{Elkin2026,
author = {Elkin, Michael and Shabat, Idan},
title = {Path-Reporting Distance Oracles with Logarithmic Stretch and Size \(O\)(\(n\) \(\log \log \) \(n\))},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {6},
pages = {1229--1292},
doi = {10.1137/24m1708954}
}
EUVIMED