Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916089037848576 |
|---|---|
| author | Elkin, Michael Trehan, Chhaya |
| author_facet | Elkin, Michael Trehan, Chhaya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_05628 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication Elkin, Michael Trehan, Chhaya Data Structures and Algorithms F.0, F.2 F.0; F.2 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. |
| title | Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication |
| topic | Data Structures and Algorithms F.0, F.2 F.0; F.2 |
| url | https://arxiv.org/abs/2401.05628 |