Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Abstract

Given an $n$-vertex $m$-edge digraph $G = (V,E)$ and a set $S \subseteq V$, $|S| = n^σ$ (for some $0 < σ\le 1$) of designated sources, the $S \times V$-direachability problem is to compute for every $s \in S$, the set of all the vertices reachable from $s$ in $G$. Known naive algorithms for this problem either run a BFS/DFS separately from every source, and as a result require $O(m \cdot n^σ)$ time, or compute the transitive closure of $G$ in $\tilde O(n^ω)$ time, where $ω< 2.371552\ldots$ is the matrix multiplication exponent. Hence, the current state-of-the-art bound for the problem on graphs with $m = Θ(n^μ)$ edges in $\tilde O(n^{\min \{μ+ σ, ω\}})$. Our first contribution is an algorithm with running time $\tilde O(n^{1 + \tiny{\frac{2}{3}} ω(σ)})$ for this problem, where $ω(σ)$ is the rectangular matrix multiplication exponent. Using current state-of-the-art estimates on $ω(σ)$, our exponent is better than $\min \{2 + σ, ω\}$ for $\tilde σ\le σ\le 0.53$, where $1/3 < \tilde σ< 0.3336$ is a universal constant. Our second contribution is a sequence of algorithms $\mathcal A_0, \mathcal A_1, \mathcal A_2, \ldots$ for the $S \times V$-direachability problem. We argue that under a certain assumption that we introduce, for every $\tilde σ\le σ< 1$, there exists a sufficiently large index $k = k(σ)$ so that $\mathcal A_k$ improves upon the current state-of-the-art bounds for $S \times V$-direachability with $|S| = n^σ$, in the densest regime $μ=2$. We show that to prove this assumption, it is sufficient to devise an algorithm that computes a rectangular max-min matrix product roughly as efficiently as ordinary $(+, \cdot)$ matrix product. Our algorithms heavily exploit recent constructions of directed shortcuts by Kogan and Parter.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.