Multi-Source Reachability in Near-Optimal Time

Shimon Kogan Weizmann Institute, Merav Parter Weizmann Institute · 2026

Read Multi-Source Reachability in Near-Optimal Time by Shimon Kogan Weizmann Institute, Merav Parter Weizmann Institute (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25612.txt.

Introduction

Given a directed network and a set of starting nodes, which nodes can each starter reach? Shimon Kogan and Merav Parter give a near optimal deterministic algorithm for that multi source reachability problem in 2026. Running a search from every source wastes time, and full transitive closure overshoots. Their method runs in time governed by the rectangular matrix multiplication exponent, the cost of multiplying the source by node matrix against the full adjacency structure.

For dense graphs the algorithm computes reachability from a substantial polynomial number of sources in near linear time, breaking a super quadratic barrier. It also beats the best previous randomised method, which carried an extra factor in its exponent. A matching lower bound comes from a three layer graph construction showing the problem is exactly as hard as the Boolean matrix product at its core.

Catalog record

CREATORShimon Kogan Weizmann Institute, Merav Parter Weizmann Institute
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE16 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25612

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multi-Source Reachability in Near-Optimal Time Shimon Kogan Weizmann Institute, Merav Parter Weizmann Institute Abstract The multi-source reachability problem asks to compute the reachable sets from a given subset of source vertices. For n n -vertex digraphs G = ( V , E ) G=(V,E) and a subset of sources S ⊆ V S\subseteq V with | S | = n σ |S|=n^{\sigma} for some σ ∈ [ 0 , 1 ] \sigma\in[0,1] , we present a near-optimal deterministic algorithm that solves this problem in O ~ ​ ( n ω ⁡ ( σ ) ) \tilde{O}(n^{\omega(\sigma)}) time, where ω ⁡ ( σ ) \omega(\sigma) is the rectangular matrix multiplication exponent for multiplying an n σ × n n^{\sigma}\times n matrix by an n × n n\times n matrix. For dense graphs, this yields reachability from up to n 0.32 n^{0.32} sources in near-linear time, breaking the super-quadratic time barrier and improving over the state-of-the-art n 1 + 2 / 3 ​ ω ​ ( σ ) n^{1+2/3\omega(\sigma)} -time randomized algorithm of Elkin and Trehan [arXiv:2401.05628, 2024]. 1 Introduction We present a near-optimal-time algorithm for computing multi-source reachability in directed graphs. In the multi-source reachability problem, given a digraph G=(V,E) and a subset of sources S\subseteq V , one must compute, for each source s , all vertices that are reachable from s . Despite extensive research over the years [ 6 , 2 ] , no known near-optimal algorithm for this problem improves over either running BFS/DFS from each source or computing the full transitive closure. Kogan and Parter [ 5 ] showed that there is not much hope for improving the combinatorial time bound to o(|S|\cdot n^{2-o(1)}) , assuming the combinatorial BMM conjecture. Elkin and Trehan [ 3 ] recently presented an n^{1+2/3\omega(\sigma)} -time algebraic algorithm using recent constructions of reachability shortcuts [ 4 ] . We show: Theorem 1.1 . There is a deterministic algorithm that, given an n -vertex digraph G=(V,E) and a subset of sources S\subseteq V with |S|=n^{\sigma} , computes multi-source reachability in \tilde{O}(n^{\omega(\sigma)}) time, where \omega(\sigma) is the rectangular matrix multiplication exponent for multiplying an n^{\sigma}\times n matrix by an n\times n matrix. This time complexity is near-optimal. To show tightness of our time complexity, we use a simple reduction from multiplying an n^{\sigma}\times n Boolean matrix by an n\times n Boolean matrix. Consider a three-layered graph (S,V_{1},V_{2}) with |S|=n^{\sigma} , where the edges of S\times V_{1} are determined by A and the edges of V_{1}\times V_{2} are determined by B . Then computing multi-source reachability, represented by an n^{\sigma}\times n matrix C , corresponds to computing A\times B . For various algorithmic applications, it is useful to also obtain the predecessor S\times V matrix, which allows one to recover the dipaths in time linear in their lengths: Witness and Predecessor Matrices. Given an a\times b Boolean matrix A and a b\times c Boolean matrix B , a witness matrix for the matrix multiplication C=A\times B is an a\times c matrix W defined as follows: If C(i,j)=0 , set W(i,j)=0 ; if C(i,j)=1 , then W(i,j) is some index k such that A(i,k)=1 and B(k,j)=1 . For an a\times n matrix R that represents the reachability from a vertices S=\{s_{1},\ldots,s_{a}\} to all vertices V=\{v_{1},\ldots,v_{n}\} in a base graph G=(V,E) , the a\times n predecessor matrix P specifies the predecessor neighbor on some s_{i} to v_{j} path, if one exists, for every s_{i},v_{j}\in S\times V . Formally, for every s_{i},v_{j}\in S\times V with R(i,j)=1 , P(i,j)=k where (v_{k},v_{j})\in E(G) and R(i,k)=1 . If R(i,j)=0 , then P(i,j)=0 . Alon et al. [ 1 ] presented a deterministic algorithm for computing the witness matrix in nearly the same time as the matrix multiplication. Theorem 1.2 . There is a deterministic algorithm that, given binary matrices A and B of dimensions n^{\sigma}\times n and n\times n , respectively, computes the n^{\sigma}\times n witness matrix for the A\times B multiplication in \tilde{O}(n^{\omega(\sigma)}) time. 2 Multi-Source Reachability in Near-Optimal Time Notation. For a vertex v , let \mathcal{S}(v,G) be the successors of v in G (i.e., the vertices that are reachable from v in G ). Throughout, reachability is non-reflexive in the output: the trivial pair (s,s) is not included merely because of the empty path. For a given source set S\subseteq V , our objective is to output the sets \{\mathcal{S}(s,G)\}_{s\in S} . For ease of notation, for vertex subsets V_{1},V_{2} and a graph G^{\prime} with V_{1},V_{2}\subseteq V(G^{\prime}) , let E_{G^{\prime}}[V_{1}\to V_{2}] be an |V_{1}|\times|V_{2}| matrix that represents the V_{1}\times V_{2} edges in G^{\prime} . Formally, letting V_{1}=[a_{1},\ldots,a_{\ell_{1}}] and V_{2}=[b_{1},\ldots,b_{\ell_{2}}] be the vertex subsets ordered by their topological ordering in G^{\prime} , then E_{G^{\prime}}[V_{1}\to V_{2}](i,j)=\begin{cases}1,&\text{if $(a_{i},b_{j})\in E(G^{\prime})$}\\ 0,&\text{otherwise.}\end{cases} (2.1) Given two matrices A,B\in\mathbb{R}^{a\times b} , let C=A\circ B be the a\times 2b matrix obtained by concatenating the columns of matrix B to those of matrix A . That is, the first (resp., last) b columns of C correspond to matrix A (resp., B ). For a given n^{\sigma}\times n matrix P where the rows correspond to k=n^{\sigma} sources S=\{s_{1},\ldots,s_{k}\} and the columns to n vertices V=\{v_{1},\ldots,v_{n}\} , we sometimes override notation and write P(s,v) for the matrix entry in the designated row and column of s and v , respectively; that is, for s=s_{i} and v=v_{j} , we have P(s,v)=P(i,j) . Informal Description. We assume, for clarity of exposition, that the input graph G is a DAG; at the end of the section, we describe how to handle general graphs. The algorithm is recursive and works as follows. Let V=[v_{1},\ldots,v_{n}] be the topologically ordered set of vertices. Split V into two equal-size parts, V_{\ell}=[v_{1},\ldots,v_{n/2}] and V_{r}=[u_{1}=v_{n/2+1},\ldots,u_{n/2}=v_{n}] , and assume that the algorithm has already computed the S\times V_{\ell} reachability matrix, R_{\ell} , in the graph G_{\ell}=G[V_{\ell}] . By the topological ordering, any S\times V_{\ell} dipath 1 1 1 I.e., a u - v dipath for u\in S and v\in V_{\ell} . in G must be contained in G_{\ell} . The goal is then to apply the algorithm recursively to compute the S\times V_{r} reachability in some (n/2+|S|) -vertex graph G_{r} . To define G_{r} , one needs to account for the S\times V_{r} paths that go through the V_{\ell} vertices. This is done by solving the following matrix multiplication: R^{\prime}=R_{\ell}\times E_{G}[V_{\ell}\to V_{r}] . Since R_{\ell} is an |S|\times n/2 matrix and E_{G}[V_{\ell}\to V_{r}] is an n/2\times n/2 matrix, the computation of R^{\prime} takes O(n^{\omega(\sigma)}) time. The matrix R^{\prime} satisfies the following property: R^{\prime}(i,j)=1 iff there is an s_{i} to u_{j} dipath in G all of whose internal vertices are in V_{\ell} . The desired graph G_{r} is then obtained by adding the edges defined by the matrix R^{\prime} to the graph G[V_{r}] . Namely, E(G_{r})=E(G[V_{r}])\cup\{(s_{i},u_{j})~\mid~R^{\prime}(i,j)=1\} . The algorithm then recurs on the instance (S,V_{r},G_{r}) . In particular, G_{r} is not merely the induced graph G[V_{r}] ; it is G[V_{r}] augmented with shortcut edges from the sources in S to vertices in V_{r} . These shortcut edges summarize the paths whose internal vertices lie in V_{\ell} . To analyze the runtime, let T(n) be the time complexity for computing multi-source reachability from S sources to n vertices. We then have T(n)\leq 2T(n/2)+MM(|S|,n/2) , where MM(a,b) is the complexity of

Read the complete text