# Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Preprint · Michael Elkin, Chhaya Trehan

- Archive id: arxiv:2401.05628
- Published: 2024-01-11
- arXiv: https://arxiv.org/abs/2401.05628
- Source URL: https://arxiv.org/abs/2401.05628
- PDF: https://arxiv.org/pdf/2401.05628
- Provenance: arxiv

## 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 reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.