Preprint
Nov 2026
Reachability Diameter: Beyond the Square-Root Barrier, with Polynomial Hardness
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.
Hector Tierno, Shuang Yang
· 0 citations