2026-08-14T13:19:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20076 2024-05-31T13:11:12Z ddc:004 open_access

Path-Reporting Distance Oracles with Linear Size Neiman, Ofer Shabat, Idan Graph Algorithms Shortest Paths Distance Oracles 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 [M. Thorup and U. Zwick, 2001] 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 [Mendel and Naor, 2007; Shiri Chechik, 2014; Shiri Chechik, 2015] 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 [Michael Elkin et al., 2016; Michael Elkin and Seth Pettie, 2016] 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(log log 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(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 [Michael Elkin and Seth Pettie, 2016]. 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|). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ofer Neiman and Idan Shabat 2024 Is Part Of LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2024.36 urn:nbn:de:0030-drops-200760 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.36 eng https://creativecommons.org/licenses/by/4.0/legalcode