2026-09-08T02:22:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26510 2026-09-05T19:46:10Z ddc:004 open_access

Faster Algorithms for (2k-1)-Stretch Distance Oracles Kadria, Avi Roditty, Liam Fine-grained complexity Graph algorithms shortest cycle girth approximations The seminal distance oracles of Thorup and Zwick [STOC 2001, JACM 2005] provide optimal stretch/space tradeoffs. However, their O(mn^{1/k}) construction time is not optimal, and they posed the question of whether a faster construction time is possible (especially for small k). In this paper, we present the first improvement upon their construction algorithm in graphs that are not super sparse, i.e., when m = Ω(n^{1+1/k+ε}), for any ε > 0. Moreover, our construction improves upon the O(n²)-time construction of Baswana and Kavitha [FOCS 2006, SICOMP 2010], for every k > 2. By achieving the first subquadratic construction for 2 < k < 6, we resolve the open problem posed by Wulff-Nilsen [SODA 2012] of whether such subquadratic-time constructions exist. Wulff-Nilsen [SODA 2012] targeted nearly linear construction times and presented algorithms running in Õ(m + n^{1+f(k)}) time, which is near-linear whenever the graph density m exceeds the threshold n^{1+f(k)}. We obtain improved bounds on f(k) for all k > 3, and thus expand the regime of graph densities for which nearly linear construction times are achievable. In addition, for unweighted graphs, we present several new algorithms for constructing (2k - 1,β)-oracles that improve upon the results of Baswana, Gaur, Sen, and Upadhyay [ICALP 2008]. Our results are achieved through the development of several new algorithmic tools, which may be of independent interest. One of our main technical contributions is a hierarchy of parameterized distance oracles, which plays a central role in our fast construction algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avi Kadria and Liam Roditty 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.121 urn:nbn:de:0030-drops-265105 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.121 eng https://creativecommons.org/licenses/by/4.0/legalcode