Skip to content
Preprint

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

Nov 2026 · 0 citations · 21 references
Computer Science

TL;DR

A randomized algorithm is given that estimates the reachability diameter of an unweighted digraph within a factor of $n^{1/3+o(1)}$, with high probability, in $\widetilde{O}(m+n)$ time, establishing the necessity of polynomial loss for nearly-linear time algorithms.

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.

View source

Similar papers

Preprint Oct 2026

Directed Global Minimum Cut in Almost-Linear Time

We give a randomized reduction from global minimum cut in a directed graph with $n$ vertices and $m$ weighted edges to maximum-flow computations on graphs of total size $\widetilde{O}(m)$. For polynomially bounded integral weights, this yields the first almost-linear $m^{1+o(1)}$-time algorithm [vdBCK+23], improving th...

Henry L. Fleischmann, Jason Li, Thatchaphol Saranurak et al. · 3 citations · ⚡1
Preprint Oct 2026

Breaking Two Barriers for Dynamic Planar Reachability

The first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting is presented, obtaining time ${O}(n^{0.49})$ per query/update, which is the first improvement upon the exponent $2/3$ in over three decades.

A. Karczmarz, Michał Włodarczyk · 0 citations
Preprint Nov 2026

Square-Root Pass Semi-Streaming Algorithms for Digraph Problems

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...

Prantar Ghosh, Amirhossein Janfaza · 0 citations
#edge computing Preprint Nov 2026

Roundtrip All-Pairs Shortest Paths in Directed Graphs

This work presents a comprehensive study of roundtrip APSP and distance oracles, presenting several new lower and upper bounds, and presents a combinatorial algorithm that computes a stretch-$3 approximation to all-pairs roundtrip distances.

S. Chechik, Gur Lifshitz · 0 citations
Preprint Oct 2026

Unconditional Boolean Dynamic Lower Bounds from Disjointness

We prove an unconditional $\Omega((\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 redu...

Young-Kun Ko · 0 citations
Preprint Nov 2026

Near-Linear Lower Bounds for Testing Directed Acyclicity

We study testing acyclicity of directed graphs in the bounded-degree incidence-lists model, where a tester can query the outneighbors of a vertex but not its inneighbors. Despite significant effort, no tester with $o(n)$ queries is known, while the best established lower bounds are $\widetilde\Omega(n^{5/9})$ for one-s...

A. Czumaj, Pan Peng, Yu-Yang Wang · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.