arXiv preprint ·
First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted Graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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_{i}$ denotes the weight of the $i$-th heaviest edge on any shortest path between them in the current graph. For any $\varepsilon>0$, our first algorithm maintains $(1+\varepsilon,2W_{2})$-APASP in $\tilde{O}(n^{\frac{3}{2}+o(1)}m^{\frac{1}{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+\varepsilon)$-APASP algorithm of Dory, Forster, Nazari and de Vos [ICALP'24]. Our second algorithm maintains $(1+\varepsilon,2W_{1}+2W_{2})$-APASP in $\tilde{O}(n^{\frac{7}{3}})$ total update time, improving upon Chechik's $(3+\varepsilon)$-APASP algorithm [FOCS'18] for $m=Ω(n^{\frac{11}{6}})$. We also obtain two $(1+\varepsilon,2\cdot(k-1)W_{1})$-APASP algorithms with total update times $\tilde{O}(n^{2-\frac{1}{k}+o(1)}m^{\frac{1}{k}})$ and $\tilde{O}(n^{2+\frac{2}{3k-2}+o(1)})$, adapting the static $+2\sum_{i=1}^{k-1}W_{i}$-APASP algorithms of Cohen and Zwick [SODA'97 and JALG'01] and Roditty and Sapir [FSTTCS'25]. For unweighted graphs, we present $(1+\varepsilon,2)$-APASP in $\tilde{O}(n^{\frac{7}{3}})$ total update time and $(1+\varepsilon,2\cdot(k-1))$-APASP in $\tilde{O}(n^{2+\frac{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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
A Constant-Factor Approximation for Capacitated Facility Location with Outliers
Noncrossing is All You Need: Beyond Identical Delay Functions in Online Matching with Delays on General Metrics
Semidirect sums of tensors and the matrix multiplication exponent
Sublinear Metric Distortion for Matching
Incremental Open Addressing Has No Time-Space Tradeoff
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.