2026-08-25T18:47:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27202 2026-08-25T13:18:17Z ddc:004 open_access

Improved Approximation Algorithms for n-Pairs Shortest Paths Kadria, Avi Roditty, Liam Vassilevska Williams, Virginia Fine-grained complexity Graph algorithm Graph distances n pairs shortest paths all pairs shortest paths distance oracles Let G = (V, E) be a graph with n = |V| nodes and m = |E| edges. The t-Pairs Shortest Paths problem, introduced by Cohen [FOCS'93; SICOMP'99], asks to approximate the distances between t prespecified pairs of vertices. Recently, this problem has received renewed attention, particularly in the case where t = Θ(n): the n-Pairs Shortest Paths problem. In this setting, new algorithms and conditional lower bounds have been developed by Dalirrooyfard, Jin, Vassilevska Williams, and Wein [FOCS'22], and Chechik, Hoch, and Lifshitz [SODA'25]. In this paper, we present the first algorithm for the n-Pairs Shortest Paths problem in weighted undirected graphs that achieves a (2 - α)k-approximation, for constant α > 0, that runs in Õ(mn^{1/k} + n^{1 + 2/k}) time. Specifically, we present a 1.622k-approximation, improving upon the (2k - 3)-approximation of Chechik, Hoch, and Lifshitz [SODA'25] for graphs that are not super sparse, which answers in the affirmative the open question posed by them. We also develop improved approximation algorithms with better tradeoffs for unweighted graphs and dense weighted graphs that improve upon the results of Dalirrooyfard et al. and Chechik, Hoch, and Lifshitz. Our main technical contribution is the new heavy-edge technique. Using this technique, we transform an algorithm with an approximation guarantee that depends on W_{uv}, the weight of the heaviest edge on the shortest path between u and v, into an algorithm with purely multiplicative approximation that does not depend on W_{uv}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avi Kadria and Liam Roditty and Virginia Vassilevska Williams 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.66 urn:nbn:de:0030-drops-272028 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.66 eng https://creativecommons.org/licenses/by/4.0/legalcode