2026-07-22T23:50:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25130 2025-12-09T15:09:12Z ddc:004 open_access

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-Offs and Algorithms Roditty, Liam Sapir, Ariel Graph Shortest Paths Weighted Graphs Approximation Undirected Single Source Shortest-Paths Multi-Source Shortest-Paths All-Pairs Shortest-Paths SSSP MSSP MSASP APSP APASP We present a +2∑_{i=1}^{k+1} W_i-APASP algorithm for dense weighted graphs with a runtime of Õ(n^{2+1/(3k+2)), where W_i is the weight of an i^th heaviest edge on a shortest path between two vertices. Dor, Halperin and Zwick [FOCS'96 and SICOMP'00] introduced two algorithms for the commensurate unweighted +2⋅ (k+1)-APASP problem: one for sparse graphs with a runtime of Õ(n^{2-1/(k+2)} m^{1/(k+2)}) and one for dense graphs with a runtime of Õ(n^{2+1/(3k+2)}). Subsequently, Cohen and Zwick [SODA'97 and JALG'01] adapted the algorithm for sparse graphs to the weighted setting, namely a +2∑_{i=1}^{k+1} W_i-APASP algorithm with the same Õ(n^{2-1/(k+2)} m^{1/(k+2)}) runtime. We fill the nearly three decades old gap by providing an algorithm for dense weighted graphs, matching the runtime for the unweighted setting. In addition, we explore nearly additive APASP, where the multiplicative stretch is 1+ε. We present a (1+ε, min{2W₁,4W₂})-APASP algorithm with a runtime of Õ((1/ε)^{O(1)} ⋅ n^{2.15135313} ⋅ log W). This improves upon Saha and Ye [SODA'24], which had the same runtime, yet (1+ε, 2W₁)-APASP. For pure multiplicative APASP, we present a (7/3+ε)-APASP algorithm with a runtime of Õ((1/ε)^{O(1)} ⋅ n^{2.15135313} ⋅ log W). This improves, for dense graphs, the Õ(nm^{2/3}+n²) runtime of the 7/3-APASP algorithm by Baswana and Kavitha [FOCS'06 and SICOMP'10], at the cost of introducing an additional ε to the multiplicative stretch. We further view this result in a broader framework of ((3𝓁+4)/(𝓁+2) + ε)-APASP algorithms, similarly to the family of (3𝓁+4)/(𝓁+2)-APASP algorithms by Akav and Roditty [ESA'21]. This also generalizes the (2+ε)-APASP algorithm by Dory, Forster, Kirkpatrick, Nazari, Vassilevska Williams, and de Vos [SODA'24]. Finally, we show that it is possible to "bypass" an Ω̃ (n^ω) conditional lower bound by Dor, Halperin, and Zwick for α-APASP with α < 2, by allowing an additive component to the approximation (e.g. a ((6k+3)/(3k+2),∑_{i=1}^{k+1} W_i)-APASP with Õ(n^{2+1/(3k+2)}) runtime.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Liam Roditty and Ariel Sapir 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.50 urn:nbn:de:0030-drops-251309 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.50 eng https://creativecommons.org/licenses/by/4.0/legalcode