CS Paper Radar

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

Eden Koveshi, Liam Roditty, Ariel Sapir

cs.DS ·submitted 2026-11-03 10:25 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Partially Dynamic Single-Source Shortest Paths in Almost-Linear Time

cs.DS ·2026-10-05 ·Bin Cui, Hanqing Li, Xupeng Miao, Haoze Wang
similarity 0.70
Abstract · v2: Added a deterministic almost-linear-time incremental SSSP algorithm with efficient approximate path reporting

We study $(1+ε)$-approximate single-source distances in directed graphs with positive integer edge weights in $[1,W]$. For every $0<ε\le1$, we give deterministic data structures for either edge insertions or edge deletions with total update time $m^{1+o(1)}ε^{-1}\log W$, where $m\ge n$ bounds the total number of initially present and inserted edges. Both structures explicitly maintain approximate distance estimates, answer distance queries in constant time, and identify unreachable vertices exactly. The incremental structure additionally reports a simple $(1+ε)$-approximate source path $P$ in $O(|P|)$ time. Our decremental structure gives the first almost-linear-time algorithm. It improves the previous best randomized expected bound of $\widetilde O(\min\{n^2,mn^{2/3}\})$ against an oblivious adversary [BPW20]. Our incremental bound improves the $ε^{-B}$ dependence of the $B$-level recursive algorithm of [Liu26] to an explicit $ε^{-1}$ factor while retaining almost-linear dependence on $m$. Our algorithms use modified interior point methods. For edge deletions, we extend the single-pair distance framework of [vBCKLMPSS24] to all targets simultaneously. A shared potential and one dynamic minimum-ratio cut instance support global updates to the distance labels. Our main insight is that constant relative cut balance certifies approximate distances at every target. For edge insertions, we develop an analogous circulation-based formulation implemented through the dynamic minimum-ratio cycle structure of [CKLMP24]. We also give a black-box reduction from distance estimates to path reporting in incremental graphs, with $m^{1+o(1)}ε^{-1}\log W$ additional maintenance time. This reduction may be of independent interest.

0.21

Faster Deterministic All-Pairs Shortest Paths with Real Edge Weights

cs.DS ·2026-11-12 ·Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
similarity 0.68
Abstract · 33 pages. Revised proofs and presentation; streamlined the real-weight result

We give a deterministic algorithm for all-pairs shortest paths in directed $n$-vertex graphs with arbitrary finite real edge weights and no negative cycles. It computes all distances in $O(n^{2.9929729})$ worst-case time, improving both the recent deterministic bound $O(n^{2.9997})$ and the Las Vegas expected-time bound $O(n^{2.993805})$. We use a model with exact real addition, subtraction and comparison at unit cost; auxiliary integer arithmetic and indexed memory access are charged at bit cost.

0.12

Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

cs.DS ·2026-11-01 ·Yang Cao, Haoran Qi, Hanzhi Wang
similarity 0.68
Abstract

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O(mn^{k-1})$-time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has remained the fastest for every $k\geq3$ for over four decades, even when the paths must be shortest. We break this bound for every $k\geq3$ with randomized algorithms running in expected $O_k(m+n^{k-3+ω+\varepsilon})$ time for every $\varepsilon>0$, where $ω<2.372$ is the matrix multiplication exponent; this is $O_k(m+n^{k-0.62})$. For two disjoint shortest paths, we find the paths as fast as we detect them: in expected linear time on DAGs and on undirected graphs with polynomially bounded integer weights, and in expected $O(\min\{mn,n^{ω+\varepsilon}\})$ time on directed graphs whose cycles have positive weight, which on dense graphs is $o(mn)$ even for detection. All algorithms evaluate a polynomial whose monomials are the solutions: a new first-collision circuit speeds up the evaluation in DAGs, and a correlated extraction step at cuts crossed once by every path finds a solution at the cost of a constant number of evaluations.

0.20

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed Graphs

cs.DS ·2026-10-13 ·Vikrant Ashvinkumar
similarity 0.67
Abstract · More detailed AI statement. Polished exposition and fixed typos

In the restricted shortest paths problem, we are given an $n$-vertex $m$-edge directed graph $G$ whose edges are assigned two non-negative weights (or resources) called lengths and costs, a source vertex $s$, and a cost threshold $C$. The goal is to find, for each target vertex $t$, the length of the shortest $(s,t)$-path whose total cost is at most $C$. Ashvinkumar, Bernstein, and Karczmarz (SODA 2025) gave the first randomized bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm on directed graphs running in sub-$mn$ time, answering a problem posed by Bernstein (SODA 2012). We substantially improve this on two fronts, supplying a deterministic bicriteria $(1+\varepsilon,1+\varepsilon)$-approximate algorithm running in near-linear time. Our approach straightforwardly generalizes to more than two resources. For $k$ resources, a deterministic $(1+\varepsilon_1,\ldots,1+\varepsilon_k)$-approximate algorithm running in near-linear time is possible, with $\varepsilon_1=\ldots=\varepsilon_k=\varepsilon$.

0.20

A Faster Undirected Single-Source Shortest Path Algorithm

cs.DS ·2026-09-14 ·Avi Kadria, Liam Roditty
similarity 0.67
Abstract

The single-source shortest paths (SSSP) problem in graphs with non-negative edge weights is one of the most classic problems in algorithms. For decades, the best known running time in the comparison-addition model was the $O(m+n\log n)$ bound of Dijkstra's algorithm with Fibonacci heaps. Recently, Duan, Mao, Shu, and Yin (FOCS'23) gave a randomized $O(m\log^{1/2} n \log\log^{1/2} n)$-time algorithm for SSSP in weighted undirected graphs. For weighted directed graphs, Duan, Mao, Mao, Shu, and Yin (STOC'25) gave an $O(m\log^{2/3} n)$-time algorithm for SSSP. Very recently, Duan, Mao, Shu, and Yin (ICALP'26) obtained an algorithm for directed graphs whose running time matches the $O(m\log^{1/2} n \log\log^{1/2} n)$ time of the undirected case. In this paper, we present a faster algorithm for SSSP in weighted undirected graphs, giving the first improvement in running time since the FOCS'23 breakthrough of Duan, Mao, Shu, and Yin. Our algorithm runs in $O(m\log^{1/2} n \log\log^{1/4} n \log\log\log^{1/4} n)$ time, improving the previous running time by a factor of $(\frac{\log\log n}{\log\log\log n})^{1/4}$. Our main contribution is a simple and efficient tool that computes, for every vertex, its distance to the nearest vertex in a random sample; this tool may be of independent interest.

0.12

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified Framework

cs.DS ·2026-11-01 ·Jiale Chen
similarity 0.67
Abstract · Abstract shortened due to arXiv requirements

We study the $(1-\varepsilon)$-approximate maximum weight matching problem in general graphs with $n$ vertices and integer edge weights in $[1,W]$. For $W=n^{O(1)}$, we obtain faster algorithms in the semi-streaming and dynamic settings: (1) Semi-streaming: Deterministic $O(\varepsilon^{-2})$-pass and $O(\varepsilon^{-2}\log(1/\varepsilon))$-pass algorithms for unweighted and weighted matching. (2) Incremental: A deterministic algorithm for weighted matching processing $m$ edge insertions in total time $O((m\varepsilon^{-3}+n\varepsilon^{-6})\log^3 n)$. (3) Decremental: A randomized algorithm for weighted matching processing all edge deletions from an $m$-edge graph in total time $O((m\varepsilon^{-8}+n\varepsilon^{-47})\log^{O(1)}n)$ with high probability. (4) Fully dynamic: A deterministic reduction from weighted matching in general graphs to unweighted matching in bipartite graphs incurring $O(\varepsilon^{-4}\log^{O(1)}(1/\varepsilon))$ multiplicative update-time overhead, independent of $n$. Underlying these results is a unified framework that reduces the problem to repeatedly solving two simpler matching subproblems: a $(1-\varepsilon)$-approximate maximum weight matching on a sparse subgraph with $O(n/\varepsilon)$ edges, and a constant approximation on the remaining edges. The framework builds on dual entropy regularization, a smoothing technique underlying efficient solvers for packing linear programs. To handle the exponentially many odd-set constraints, we adapt the smoothing technique to regularize only the vertex duals and develop a new cut partition that preserves odd-set feasibility during optimization.

0.16

Local Representatives and Shortest Completions for Next-to-Shortest Paths in Directed Graphs

cs.DS cs.DM ·2026-09-19 ·Shisheng Li
theory similarity 0.66
Abstract · 15 pages

Given a directed graph with positive edge weights and two vertices s,t, a next-to-shortest s-t path is a shortest simple s-t path among those whose length is strictly larger than the shortest-path distance. The problem was introduced by Lalgudi, Papaefthymiou and Potkonjak in 1996; it is NP-hard when zero-weight edges are allowed, and its complexity on positively weighted digraphs remained open for almost three decades until Chen, Wein and Zhang recently gave a polynomial-time algorithm running in O(n^4 m^3 log n) time. We give a substantially faster algorithm within their optimal-middle-segment framework. The core idea is to split the problem into "choosing a prefix" and "completing it". Given a prefix P: s -> A made of shortest-path edges, delete the vertices used by P, forbid leaving A along shortest-path edges, and the best completion is one shortest-path computation. The difficulty lies in choosing P: even for a fixed A, deciding whether some shortest prefix admits a completion is NP-complete. We do not solve these fixed-A subproblems one by one. Fix any globally optimal next-to-shortest path; its middle segment induces a boundary edge x -> c in the shortest-path DAG. For the correct triple (A,B,x), the optimal path certifies c as a feasible next hop, and we prove that every feasible next hop that is not earlier than c in a topological order can be combined with the same middle segment into another globally optimal path. Hence only the feasible next hop of maximum topological index is kept per triple, giving O(n^3) representatives, all generated by a two-dimensional DAG dynamic program with a local reward. The total running time is O(n^3 (m + n log n)), and O(n^3 m) on unweighted graphs. The proof rests on an uncrossing lemma: the last intersection between a reference prefix and the candidate's partner suffix can always be moved strictly earlier, which cannot go on forever.

0.21

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.65
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25