First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs

We present the first four All-Pairs Approximate Shortest Paths (APASP) algorithms for decremental weighted undirected graphs. We extend the hierarchy induced edge sets of Baswana and Kavitha [FOCS'06 and SICOMP'10] to the decremental setting. At any point in time, for any $u,v$, Wᵢ denotes the weight of the i-th heaviest edge on any shortest path between them in the current graph. For any ε>0, our first algorithm maintains (1+ε,2W₂)-APASP in Õ(n3/2+o(1)m1/2) total update time, matching a single static computation of Cohen and Zwick [SODA'97 and JALG'01], up to a subpolynomial factor. It also improves the stretch of the (2+ε)-APASP algorithm of Dory, Forster, Nazari and de Vos [ICALP'24]. Our second algorithm maintains (1+ε,2W₁+2W₂)-APASP in Õ(n7/3) total update time, improving upon Chechik's (3+ε)-APASP algorithm [FOCS'18] for m=Ω(n11/6). We also obtain two (1+ε,2·(k-1)W₁)-APASP algorithms with total update times Õ(n2-1/k+o(1)m1/k) and Õ(n2+2/3k-2+o(1)), adapting the static +2∑ᵢ₌₁ᵏ⁻¹Wᵢ-APASP algorithms of Cohen and Zwick [SODA'97 and JALG'01] and Roditty and Sapir [FSTTCS'25]. For unweighted graphs, we present (1+ε,2)-APASP in Õ(n7/3) total update time and (1+ε,2·(k-1))-APASP in Õ(n2+1/3k-4+o(1)). Combined with the results of Dory, Forster, Nazari and de Vos [ICALP'24], these match the fastest combinatorial static bounds of Dor, Halperin and Zwick [FOCS'96 and SICOMP'00] up to subpolynomial factors.