CS Paper Radar

Improved Bounds for Directed SSSP in Sparse and Intermediate-Density Graphs

Valery, Grishin, Aryeh Lev Zabokritskiy

cs.DS ·submitted 2026-11-19 17:20 UTC · v1

Abstract

We give a deterministic algorithm for exact single-source shortest paths (SSSP) in directed graphs with $n$ vertices, $m$ edges and nonnegative real edge weights. In the comparison-addition model, with unit-cost elementary operations on $O(\log(n+m+2))$-bit integer words, its running time for $m=O(n)$ is $O(n\sqrt{\log n}(\log\log n)^{1/4})$. For $m=Θ(n)$, this reduces the exponent of $\log\log n$ in the bound of Duan, Mao, Shu and Yin from $1/2$ to $1/4$ and removes the factor $(\log\log\log n)^{1/4}$ from the sparse bound stated in a public draft. The same algorithm improves on the bound of Duan et al. over a range of intermediate densities. At $m=Θ(n\sqrt{\log\log n})$, the running time is $O(n\sqrt{\log n}(\log\log n)^{5/8})$, reducing their exponent from $3/4$ to $5/8$. This is a consequence of a uniform bound for intermediate densities up to any fixed multiple of $n\log\log n$ edges; its validity range is larger than the range of strict improvement.

Comment
69 pages

Closest papers

Nearest neighbours by meaning across the whole index.

A Faster Undirected Single-Source Shortest Path Algorithm

cs.DS ·2026-09-14 ·Avi Kadria, Liam Roditty
similarity 0.78
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

Improved Massively Parallel Shortest Path Computation

cs.DC cs.DS ·2026-10-12 ·Yi-Jun Chang, Shaun Quek
hot direction similarity 0.67
Abstract

We present new algorithms for approximate shortest path computation in weighted undirected graphs within the Massively Parallel Computation (MPC) model. Specifically, we construct an $a$-approximate Single-Source Shortest Path (SSSP) oracle: Given a query consisting of a source vertex $u \in V$, the oracle returns $a$-approximate distances $δ(u,v)$ for all $v \in V$. Fix an $n$-vertex weighted undirected graph. We consider two regimes of the MPC model: the near-linear regime, where each machine has $\tildeΘ(n)$ memory, and the heterogeneous regime, where all machines have $Θ(n^γ)$ memory for some constant $γ\in (0,1]$, except for a single machine with $\tildeΘ(n)$ memory. We develop randomised algorithms that construct $O(1)$-approximate SSSP oracles in $O(\log\log n)$ rounds in the near-linear regime and in $O(\log^2\log n)$ rounds in the heterogeneous regime. These oracles answer distance queries in $O(1)$ rounds. Our results improve upon the recent work of Dory and Matar (SPAA 2024) which, for the same total memory, requires $\left(\log\log n\right)^{2+O(1/γ)}$ rounds and applies only to unweighted graphs in the heterogeneous setting. We say that $\tilde N_k(u)$ is the approximate $k$-nearest neighbourhood of a vertex $u$ if there exists an approximate distance estimate $δ$ such that $\tilde N_k(u)$ consists of the $k$ vertices closest to $u$ according to $δ$, breaking ties by vertex ID. The main technical ingredient is a new method for efficiently computing approximate $n^{O(γ)}$-nearest neighbourhoods in the heterogeneous MPC model in $O(\log^2\log n)$ rounds.

0.31

Approximating the Girth of an Undirected, Weighted Graph for Larger Approximation Factors

cs.DS ·2026-10-16 ·Eliyahu Yablon
similarity 0.67
Abstract

The girth of a weighted undirected graph is defined as the length of a shortest cycle in the graph. In this paper, we give a randomized $O\left(m^{1+2/(k-1)} n^{1/(k-1)}\right)$ algorithm to approximate the girth of a graph with $n$ vertices and $m$ edges to within a factor of $k$ for any real $k$. We assume that all edge weights are non-negative. For sufficiently high approximation factors, our algorithm outperforms the state of the art by polylogarithmic factors. Specifically, for approximation factors $k = c\frac{\log n}{\log \log n}$ where $c>5$, our algorithm gives a runtime of $O\left(m (\log n)^{5/c}\right)$, while instantiating the previous best $k$-approximation algorithms with $k = c\frac{\log n}{\log \log n}$ yields a running time of $O\left( \frac{cn (\log n)^{2 + 4/(3c)} }{\log \log n} + m\log n\right)$ (Kadria, Roditty, and Vassilevska Williams, arXiv:2607.00938). Furthermore, the algorithm presented here is conceptually simple, has relatively small constants, eschews single-source shortest path and sparse spanner algorithms, and employs a new technique, which we call ``random filtering.'' That being said, the basic algorithm returns only a numerical estimate for the girth, rather than a witness cycle.

0.18

Unconditional Boolean Dynamic Lower Bounds from Disjointness

cs.DS cs.CC ·2026-10-07 ·Young Kun Ko
theory similarity 0.66
Abstract · 48 pages, 3 figures. v2: main result stated for the multiphase problem; appendix extended to further dynamic problems; introduction revised.…

We prove an unconditional $Ω((\log n/\log\log n)^2)$ lower bound on the maximum of the worst-case update time and expected query time for the insert-only version of Patrascu's multiphase Disjointness problem [STOC 2010]. The bound holds in the zero-error cell-probe model with logarithmic word size. Patrascu's reductions transfer it to directed reachability under edge insertions, already on directed acyclic graphs of depth $2$. This improves the $\widetildeΩ(\log^{3/2} n)$ bound of Larsen and Yu [SICOMP 2025] to the quadratic-logarithmic scale previously attained for dynamic range counting and multiphase Inner Product. The bound also transfers to a broad collection of dynamic graph, algebraic, geometric, and string problems. We also obtain a separation between amortized and worst-case time for streaming regular-expression membership. For a simple family of expressions of maximum length $M$ over a polynomial-size alphabet, a deterministic algorithm uses $O(1)$ amortized time per symbol on every input stream, whereas every zero-error cell-probe algorithm with word size $w=Θ(\log M)$ requires $Ω((\log M/\log\log M)^2)$ time on some symbol. The proof adapts Ko's 2.5-round multiphase communication framework [FOCS 2026] from Inner Product to Disjointness. Our main technical observation is that the protocol's verification step allows a one-sided corruption bound to replace the discrepancy property used for Inner Product.

0.24

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

cs.DS ·2026-11-02 ·Prantar Ghosh, Amirhossein Janfaza
theory similarity 0.66
Abstract

We study directed graph problems in the semi-streaming model where we are restricted to $\widetilde{O}(n):=O(n\cdot \text{polylog}(n))$ space for processing the edge stream of an $n$-node graph and can make one or a few passes to solve the given problem. A longstanding open problem in multipass streaming is determining the number of semi-streaming passes needed to solve directed $s,t$-reachability: there is an exponential gap---$Ω(\log n/\log \log n)$ vs $n^{1/2+o(1)}$---between the best-known lower and upper bounds. Several related fundamental digraph problems, e.g., topological sorting, acyclicity testing, and decomposition into strongly connected components (SCCs), are known to have the same semi-streaming pass lower bound. However, no $o(n/\text{polylog}(n))$-pass upper bound was known for any of them. Our main result achieves an $n^{1/2+o(1)}$-pass semi-streaming algorithm for each of these problems. As a corollary, we get algorithms with the same pass and space usage for a broad class of DAG problems that admit a certain form of dynamic program over a topological ordering. This class includes weighted single-source shortest paths, longest paths, max-outdegree+1 coloring, and constructing a lexicographically-first DFS (depth-first search) forest. Our algorithm for the last problem can be seen as a generalization of our results on topological sorting and acyclicity testing: recall that standard textbook algorithms for these problems use DFS as a subroutine. Our algorithms are optimal up to an $n^{o(1)}$ factor in passes under the reasonable conjecture that $s,t$-reachability requires $Ω(\sqrt{n})$ semi-streaming passes. However, using the fact that our algorithms can be parameterized by the number of passes taken by topological sorting or single-source reachability algorithms, we prove stronger lower bounds for some of the problems even under weaker conjectures.

0.28

Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness

cs.DS ·2026-11-03 ·Hector Tierno, Shuang Yang
theory similarity 0.64
Abstract

The reachability diameter of a directed graph is the maximum finite shortest-path distance across all pairs of vertices. It has received recent attention under this name, although the underlying quantity has long played a central role in shortcut set and parallel reachability. Notably, Bals et al. establish hardness for every polynomial-factor approximation in nearly-linear time for weighted digraphs. Yet they give $n^{1/2+o(1)}$-approximation in the unweighted regime with nearly-linear running time, and their conditional lower bounds rule out certain constants only, leaving open whether polynomial loss is necessary. We give a randomized algorithm that estimates the reachability diameter of an unweighted digraph within a factor $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time. We complement our algorithm with a lower bound conditional on the 3-uniform Hyperclique hypothesis, ruling out an $n^{2/15-\varepsilon}$-approximation in $\widetilde{O}(m+n)$ time for every fixed $\varepsilon\in(0,2/15)$, establishing the necessity of polynomial loss for nearly-linear time algorithms.

0.25

Deterministic Girth Approximation in Weighted Undirected Graphs

cs.DS ·2026-10-09 ·Avi Kadria
similarity 0.64
Abstract

We give deterministic algorithms for approximating the girth~$g$ of an undirected graph with $n$ vertices, $m$ edges, and nonnegative real edge lengths. For every integer $k\geq2$, our algorithm returns a cycle of length at most $\frac{2k}{3}g$ in $O((m+n^{1+2/k})k\log n)$ worst-case time. For every constant~$k$, this matches the stretch and the expected running time of the randomized algorithms of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'23, SICOMP'26] and Kadria, Roditty, and Vassilevska Williams [ESA'26]. In general, it loses only a factor of $O(\min\{k,\log n\})$ in the term that depends on~$m$. The best previous deterministic trade-off, of Kadria, Roditty, Sidford, Vassilevska Williams, and Zwick [SODA'22], has stretch~$k$ instead of $\frac{2k}{3}$ at the same exponent (for even~$k$) and requires integer edge lengths. In particular, for $k=3$ we obtain a deterministic $2$-approximation in $O((m+n^{5/3})\log n)$ time for real edge lengths, whereas the deterministic algorithm of Ducoffe [SIDMA'21] for real lengths has stretch $2+\varepsilon$. Our main technical idea is that a deterministic construction of the Thorup--Zwick hierarchy used by these algorithms may stop exploring as soon as it finds a cycle: the approximation analysis only needs clusters truncated at half the best cycle certificate found, so balls stopped in this way need not be hit. Together with a degree-weighted selection rule, this bounds the work of each level by its number of edges and stored ball entries. More generally, a ball need not be hit whenever the analysis only uses clusters up to a radius bounded by a certificate that the algorithm has already found.

0.44

Reading between the levels: new tools for the Thorup-Zwick hierarchy and their applications

cs.DS ·2026-10-31 ·Shiri Chechik, Gur Lifshitz, Avi Kadria, Liam Roditty
similarity 0.64
Abstract

In this paper, we develop three new analytical tools for the Thorup-Zwick hierarchy: the Mixed-Level Growth, Two-Level Growth, and Long-Short Growth lemmas. Using these tools, we obtain improved approximate distance oracles (ADOs), and algorithms for $n$-pairs shortest paths ($n$-PSP), multiple-source shortest paths (MSSP), and $ST$-shortest paths, as well as new hopsets. One of our main results is a $(\frac 65 k+O(1))$-stretch ADO with $\tilde O(mn^{1/k})$ preprocessing time and space (where $\tilde O$ hides polylogarithmic factors), and $\tilde O(n^{1/k})$ query time, breaking, for sparse graphs, the $(2k-O(1))$-stretch barrier for ADOs with $\tilde O(n^{1+1/k})$ space and $\tilde O(n^{1/k})$ query time. In unweighted graphs, we also obtain a $(\frac 65 k+O(1),O(k))$-approximate ADO with $\tilde O(n^{1+1/k})$ space and $\tilde O(n^{1/k})$ query time. This also yields a $(\frac 65 k+O(1))$-approximation algorithm for $m$-pairs shortest paths ($m$-PSP) in $\tilde O(mn^{1/k})$ time, answering the question of Chechik, Hoch, and Lifshitz [SODA'25] of whether the $2k-O(1)$ barrier for $n$-PSP in $\tilde O(mn^{1/k})$ time can be broken. For unweighted graphs, we give a new analysis of the existing $\tilde O(mn^{1/k}+n^{1+2/k})$-time $n$-PSP algorithm of [Chechik et al., SODA'25], and show that, without any modification, it is a $(k,k-1)$-approximation, i.e., $d(u,v)\le\hat d(u,v)\le k\cdot d(u,v)+k-1$ for every queried pair. This improves its multiplicative factor from $\frac 43 k+O(1)$ to $k$, and the leading coefficient $k$ is tight for this algorithm. Moreover, for graphs with $m=Ω(n^{1+1/k})$, this answers the question of Dalirrooyfard et al. [FOCS'22] up to the additive $k-1$.

0.21