Parallel Reachability and Shortest Paths on Non-Sparse Digraphs: Near-Linear Work and Sub-Square-Root Depth

The two most basic algorithms for parallel reachability are (i) using parallel matrix multiplication to compute the transitive closure of $G$ which, while highly parallel with $\text{polylog}(n)$ depth, is not remotely work-efficient; and (ii) using parallel BFS which, while work-efficient, unfortunately has span proportional to the depth of the BFS-tree of $G$, which is $\mathrm{\Omega }(n)$ on worst-case inputs. Until somewhat recently, no nearly work-efficient algorithm with sublinear depth had been known. The breakthrough of Fineman [8] gave the first nearly work-efficient algorithm with sublinear depth $\tilde{O}(n^{2/3})$. This was then built upon by Jambulapati, Liu, and Sidford [11] to give a nearly work-efficient algorithm with $n^{1/2+o(1)}$ depth, which remains the best known upper bound. This algorithm can also be generalized to give a work-span tradeoff [7].

Both [8, 11] utilize a framework based on shortcut sets, which dates back to [19]. A $\beta$-shortcut set of $G$ is a set $H\subseteq V\times V$ such that the reachability relations of $G$ and $G\cup H$ are the same, and for any $u,v\in V$ such that $u$ reaches $v$, there is a path from $u$ to $v$ using at most $\beta$ hops in $G\cup H$. Given a $\beta$-shortcut set $H$, one may compute single-source reachability in $O(m+\left|H\right|)$ work and $O(\beta )$ depth by computing a parallel BFS on $G\cup H$ from source $s$. There is a folklore construction of an $O(\sqrt{n})$-shortcut set $H$ with $\left|H\right|=\tilde{O}(n)$: randomly sample $\tilde{O}(\sqrt{n})$ vertices and add all shortcut edges $uv$ where $u$ and $v$ are sampled vertices such that $u$ can reach $v$ in $G$. This was (at the time of [8, 11]) the best known existential bound, but no efficient algorithmic constructions meeting these bounds were known, even in the sequential setting. The breakthrough of [8] was a nearly work-efficient construction of an $\tilde{O}(n^{2/3})$-shortcut set with linear size. [11] then gave the first nearly work-efficient construction of a shortcut set that essentially matches the folklore bound. The key technical contribution to both results was the first near-linear time sequential construction of said shortcut sets, which they then showed how to parallelilize.

Both [8] and [11] construct a shortcut set $H$ with only $\tilde{O}(n)$ edges. But for many problems, and for parallel reachability in particular, a shortcut set with $\tilde{O}(m)$ edges would do just as well. For non-sparse graphs, allowing $H$ to contain more edges is conceptually advantageous because the folklore construction can be tuned to achieve a $O(n/\sqrt{m})$-shortcut set $H$ with $\left|H\right|=\tilde{O}(m)$, by simply sampling more vertices. Unfortunately, the constructions of [8, 11] are not so readily tunable in this way, so we do not have any efficient algorithmic constructions of these denser hopsets, even in the sequential settings. In this paper, we give a near-linear time sequential construction of an $\tilde{O}(m)$ size $\beta$-shortcut set where $\beta$ scales with the density of the base graph; for any $m$ polynomially larger than $n$, we achieve $\beta$ polynomially better than $\sqrt{n}$. We can further improve the tradeoff with fast matrix multiplication: at the extreme case, if $\omega =2$, our construction essentially matches the bounds of the tuned folklore construction, generalizing [11]. We then show that all our sequential bounds can be easily parallelized, leading to nearly work-efficient parallel reachability algorithms with significantly lower depth in non-sparse graphs.

Rozhoň ⓡ²²2A randomized author ordering generated in the cited work is delimited by ⓡ separators. Haeupler ⓡ Martinsson ⓡ Grunau ⓡ Zuzic [17] gave a blackbox reduction from SSSP to single-source $(1+\epsilon )$-approximate shortest paths, so we focus on the latter.

A similar framework to computing shortcut sets followed by parallel BFS is viable for approximate shortest paths. Instead of BFS, one uses an algorithm of Klein and Subramanian [12] for finding (exact) shortest $\beta$ hop paths in $\tilde{O}(m)$ work and $\tilde{O}(\beta )$ span. And instead of a $\beta$-shortcut set, one constructs a so-called $(\beta ,\epsilon )$-hopset of $G$ which is a set $H\subseteq V\times V$ such that ${\mathrm{dist}}_G(u,v)\le {\mathrm{dist}}_{G\cup H}^{\left(\beta \right)}(u,v)\le (1+\epsilon ){\mathrm{dist}}_G(u,v)$ for all $u,v\in V$, where ${\mathrm{dist}}^{\left(\beta \right)}$ is the length of the shortest path using at most $\beta$ hops. The folklore shortcut set is easily adapted to showing the existence of $(O(\sqrt{n}),\epsilon )$-hopsets $H$ with $\left|H\right|=\tilde{O}(n)$. Analogously, Cao, Fineman, and Russell [6] adapted the shortcut set construction of [11] to give a near-linear time construction of an $(n^{1/2+o(1)},\epsilon )$-hopset $H$ with $\left|H\right|=\tilde{O}(n)$, essentially meeting this folklore bound. A work-span tradeoff was then later given in [7].

Just as with shortcut sets, the requirement that $\left|H\right|=\tilde{O}(n)$ is sometimes too stringent. The folklore hopset can in the same way be tuned to give an $(O(n/\sqrt{m}),\epsilon )$-hopset $H$ with $\left|H\right|=\tilde{O}(m)$ by sampling more vertices, but the hopset of [6] does not immediately generalize in this way. In this paper, we give a near-linear time sequential construction of an $\tilde{O}(m)$ size $(\beta ,\epsilon )$-hopset where $\beta$ scales with the density of the base graph. This is then parallelized and plugged into the abovementioned framework to get faster nearly work-efficient parallel SSSP algorithms.

Our main result is on parallel reachability.

Using the fact that (by [1] and Proposition 5), we can compute reachability in $\tilde{O}(m)$ work and $n^{0.86461}/m^{0.36461}$ span ($n^{0.136}$ span when $m=\mathrm{\Omega }(n^2)$). The previous best span for nearly work-efficient algorithms for reachability was at least $\mathrm{\Omega }(\sqrt{n})$, regardless of digraph density: [11] achieves depth $n^{1/2+o(1)}$, while the min-cost flow algorithm of [4] reduces the depth to $\tilde{O}(\sqrt{n})$ when $m\gtrsim n^{1.5}$.

The technical developments used to get the parallel reachability algorithm of Theorem 1 is largely a near-linear time sequential construction for a $\sqrt[2\omega -2]{n^{\omega +o(1)}/m}$-shortcut set with size $\tilde{O}(m)$.

Refer to Table 1 for the spans of our algorithms given for different values of $\omega$ shown in a tabular format, summarizing Theorem 1 and Theorem 2. Of particular interest are the extremes where Theorem 2 outputs, if $\omega =3$, a combinatorially constructed $n^{3/4+o(1)}/m^{1/4}$-shortcut set and, if $\omega =2$ an $n^{1+o(1)}/\sqrt{m}$-shortcut set almost matching the tunable folklore shortcut set in its parameters. Also of note: the tradeoff given by Theorem 2 is strictly better than that given by [7], which is a randomized $\tilde{O}\left(m{\varrho }^2+n{\varrho }^4\right)$ time construction of an $n^{1/2+o(1)}/\varrho$-shortcut set $H$ with size $\tilde{O}(n{\varrho }^2)$; most crucially, because of the $m{\varrho }^2$ term, their tradeoff could not achieve near-linear work for any graph density.

Parallelizing the previous state-of-the-art near-linear size $n^{1/2+o(1)}$-shortcut set of [11] was, while important, somewhat tedious. Using the new technology of [9], we can easily parallelize Theorem 2 – see Theorem 16 for details – and consequently use the parallel construction to immediately get our main result Theorem 1.

We then show analogous results for SSSP, albeit with slightly weaker bounds. The details of these results can be found in the full version.

On dense digraphs, this gives a nearly work-efficient $n^{1/4+o(1)}$ span algorithm for SSSP. The previous best span for nearly work-efficient algorithms for SSSP was at least $\mathrm{\Omega }(\sqrt{n})$, similar to the previous state of reachability: [17, 5] achieve depth $n^{1/2+o(1)}$, while the min-cost flow algorithm of [4] reduces the depth to $\tilde{O}(\sqrt{n})$ when $m\gtrsim n^{1.5}$.

Analogously to parallel reachability, the main driver of Theorem 3 is a near-linear time sequential construction of a $(\sqrt[4]{n^{3+o(1)}/m},\epsilon )$-hopset $H$ with size $\tilde{O}(m/{\epsilon }^2)$.

In particular, Theorem 4 on dense digraphs runs in $\tilde{O}(n^2/{\epsilon }^2)$ time and shortcuts $(1+\epsilon )$-approximate shortest paths to $n^{1/4+o(1)}$ hops, whereas the previous best hop bound was $n^{1/2+o(1)}$ given by [6] for all density regimes. Similarly to shortcut sets, the tradeoff of Theorem 4 is strictly better than (the sequential version) of [7].

We get Theorem 3 by parallelizing Theorem 4, again simply, using the new technology of [9] – see the full version for details on said parallelization.

Due to technical complications described in the full version, not all of the ideas used for shortcut sets (Theorem 2) go through for constructing hopsets (Theorem 4). Nevertheless, the main conceptual ideas do indeed go through, allowing us to match the bound in the combinatorial version of Theorem 2, i.e. when $\omega =3$ (see Table 1 for more on the combinatorial version).

There exists a rich literature on shortcut sets and hopsets with stronger existential bounds than the folklore construction [14, 13, 3, 15, 16] though currently no near-linear time construction of is known, even in the sequential setting. In particular, the breakthrough of [14] showed the existence of a $\sqrt[3]{n^2/m}$-shortcut set with size $\tilde{O}(m)$ which, if constructible in near-linear work, would give a depth $\sqrt[3]{n^2/m}\ll n/\sqrt{m}$ algorithm for reachability. Along another direction, [2] recently showed a deterministic construction of an $O(\sqrt{n})$-shortcut set with size $O(n{\log }^{\ast }n)$ in almost-linear time. We include a more detailed discussion of these related works in the full version.

To bound the diameter of JLS, we fix an arbitrary path $P$ and show that $P$ is shortcut to length $n^{1/2+o(1)}$. First, observe that at any fixed recursion level, say $r$, the path $P$ is split into contiguous subpaths $P_1,P_2,\mathrm{\dots }$ each belonging to distinct level $r+1$ recursive instances $G_1,G_2,\mathrm{\dots }$ respectively. To see this, note that if a pivot vertex reaches (resp. is reached by) any two vertices in $P$, then it reaches (resp. is reached by) every vertex on the subpath between said two vertices in $P$; thus, if $x$ and $y$ are in the same subproblem $G_i$, then so are all the vertices on any path from $x$ to $y$. (See Observation 8 for the formal proof.)

We use this observation to define the subproblem tree of $P$, which tracks how $P$ is shortcut. (i) The root node⁴⁴4Here and throughout, we use “node” to refer to the nodes of subproblem trees, which are analysis tools which our algorithms are not aware of, and “vertex” to refer to the vertices of digraphs, which are the objects our algorithms interface with. of this tree, at level $0$, is $P$; (ii) If a bridge of a level $r$ node $P^{\prime }$ is selected in the recursion level $r$ instance $G^{\prime }$ (in which $P^{\prime }$ is contained) then $P^{\prime }$ is a leaf node and, otherwise, $P^{\prime }$ has level $r+1$ children nodes $P_1^{\prime },P_2^{\prime },\mathrm{\dots }$ corresponding to how $P^{\prime }$ is split. The reader should observe that each leaf $P^{\prime }$ is shortcut to $O(1)$ hops (moving through the bridge of $P^{\prime }$) and, hence, the number of nodes in the subproblem tree upper bounds the number of hops $P$ is shortcut to (up to a constant factor).

[11] shows that the number of nodes in the subproblem tree of any path $P$ is bounded above by $n^{1/2+o(1)}$. Crucially, they use the following key lemma within a bottom-up argument by induction:

where $P^{\prime }$ (in subproblem $G^{\prime }$) is an arbitrary internal node in the subproblem tree and $S$ are the pivots selected in $\mathrm{R}(G^{\prime },P^{\prime })$ that split $P^{\prime }$ into subpaths $P_1^{\prime },P_2^{\prime },\mathrm{\dots },P_{\left|S\right|+1}^{\prime }$ in subproblems $G_1^{\prime },G_2^{\prime },\mathrm{\dots },G_{\left|S\right|+1}^{\prime }$ respectively. Recall (from Section 2) that $\mathrm{R}(G^{\prime },P^{\prime })$ are the vertices in $G^{\prime }$ that can reach or are reached by some vertex in $P^{\prime }$.

We suggest that Proposition 11 is best interpreted in the following way. Intuitively, splitting a path $P^{\prime }$ into $P_1^{\prime },P_2^{\prime },\mathrm{\dots },P_{\left|S\right|+1}^{\prime }$ is detrimental to shortcutting $P^{\prime }$ (and hence $P$) since the algorithm will no longer be able to add any shortcut between $P_i^{\prime }$ and $P_j^{\prime }$ for $i\ne j$. For example, if $\left|S\right|\gg n^{1/2+o(1)}$, then there would no longer be any hope of shortcutting $P$ to $n^{1/2+o(1)}$ hops. On the other hand, Proposition 11 shows that splitting a path still offers progress: the number of relevant vertices to $P^{\prime }$ drops significantly. Since $P^{\prime }\subseteq {\bigcup }_{i=1}^{\left|S\right|+1}\mathrm{R}(G_i^{\prime },P_i^{\prime })$ and each $v\in P^{\prime }$ is a bridge of some $P_i^{\prime }$, the fraction of bridges increases⁵⁵5This is not entirely true, since bridges of $P^{\prime }$ may cease to be bridges of $P_i^{\prime }$ for any $i$.. It is consequently more likely to select bridges as pivots and shortcut the subpaths that $P^{\prime }$ is split into to $O(1)$ hops each.

For simplicity’s sake, let us assume something stronger than Proposition 11: that the typical scenario occurs deterministically.

Assuming Idealized Proposition 11 above does not change any structure of our argument and only removes clutter related to formalization of probabilistic guarantees.

Given this, we first bound the number of nodes in the subproblem trees.

Assume the input digraph is dense – that is, it has $\mathrm{\Omega }(n^2)$ edges. Denote ${\text{BFS}}_{\sqrt{n}}(G^{\prime },v)$ as the first $\sqrt{n}$ vertices found in a BFS in $G^{\prime }$ starting from $v\in V(G^{\prime })$.

Here is a simple modification to the JLS algorithm. For each recursive subproblem $G^{\prime }$ and each $v\in V(G^{\prime })$, add all the following edges to the shortcut set: edges from $v$ to ${\text{BFS}}_{\sqrt{n}}(G^{\prime },v)$.

Note that ${\text{BFS}}_{\sqrt{n}}(G^{\prime },v)$ runs in $O(n)$ time, totaling up to $\tilde{O}(n^2)$ time over all the calls made in all recursive subproblems. This additional step thus gives a negligible overhead to the running time of JLS.

Crucially, for any node $P^{\prime }=⟨v_0,v_1,\mathrm{\dots },v_h⟩$ in the subproblem tree with , the edge $v_0{v}_h$ will be added to the shortcut set since $v_h\in {\text{BFS}}_{\sqrt{n}}(G^{\prime },v_0)$. Namely, $P^{\prime }$ is shortcut to $O(1)$ hops and is removed from the pruned subproblem tree which, accordingly, has $O(n^{1/4+o(1)})$ nodes by Claim 6 (which, recall, upper bounds the length $P$ is shortcut to).

In summary, this simple modification to JLS gives a near-linear time construction of an $O(n^{1/4+o(1)})$-shortcut set on dense digraphs $G$.

Our main result for reachability does not use the combinatorial improvement above, but instead utilizes fast matrix multiplication. Here we just briefly summarize the idea and leave the details to Section 4. Instead of computing ${\text{BFS}}_{\sqrt{n}}(G^{\prime },v)$ from each $v\in V(G^{\prime })$ in every recursive subproblem $G^{\prime }$ as in our warmup, we get even more of a speed up from loosely speaking computing shortcuts in an “all-pairs” fashion (i.e. transitive closures). This is easier said than done since one call to a transitive closure algorithm is more expensive than one BFS call; we must thus be judicious of when and on what vertices to call the transitive closures (instead of from every vertex like we did with BFS).

When $\left|\mathrm{R}(G^{\prime },P^{\prime })\right|$ is small (at the threshold where we wish to prune away the node $P^{\prime }$ from the subproblem tree of $P$), one might try to call a transitive closure on a ball centered at $v$ for some $v\in P^{\prime }$. The flaw in this idea is that the choices made by the algorithm must be oblivious to $P^{\prime }$. A more oblivious approach would be to call a transitive closure on $\mathrm{R}(G^{\prime },p)$ for some pivot $p\in \mathrm{R}(G^{\prime },P^{\prime })$. However, $\left|\mathrm{R}(G^{\prime },p)\right|$ is not necessarily the same as $\left|\mathrm{R}(G^{\prime },P^{\prime })\right|$ since $p$ may not be a vertex in $P^{\prime }$. In fact, $p$ may reach or be reached by many vertices that have no reachability relation to $P^{\prime }$, and hence $\left|\mathrm{R}(G^{\prime },p)\right|$ might be very large despite $\left|\mathrm{R}(G^{\prime },P^{\prime })\right|$ being very small; calling a transitive closure on $\left|\mathrm{R}(G^{\prime },p)\right|$ may then be too expensive!

Instead, we do the following. For every pivot $p$, if $\left|\mathrm{R}(G^{\prime },p)\right|$ is small enough, we add all edges in the transitive closure of $\mathrm{R}(G^{\prime },p)$ to the shortcut set. This can be done in $\tilde{O}({\left|\mathrm{R}(G^{\prime },p)\right|}^{\omega })$ time by repeatedly squaring the adjacency matrix of $G^{\prime }[\mathrm{R}(G^{\prime },p)]$. By virtue of $\left|\mathrm{R}(G^{\prime },p)\right|$ being small, we have control over the running time of this improvement. Moreover, since all edges in the transitive closure of $\mathrm{R}(G^{\prime },p)$ are added to the shortcut set, $p$ would not contribute any children to the node $P^{\prime }$. But would it allow us to prune the node $P^{\prime }$ completely when $\left|\mathrm{R}(G^{\prime },P^{\prime })\right|$ is small? Not quite. We show in Section 4 that it allows us to prune nodes in the subtree rooted at $P^{\prime }$ so that the pruned subtree has $O(\log n)$ nodes; loosely, the argument is as follows: for any node $P^{\prime \prime }$ in this subtree, if all $p\in \mathrm{R}(G^{\prime \prime },P^{\prime \prime })$ have small $\left|\mathrm{R}(G^{\prime \prime },p)\right|$ then $P^{\prime \prime }$ has at most one child and, otherwise, there is some $p\in \mathrm{R}(G^{\prime \prime },P^{\prime \prime })$ with large $\left|\mathrm{R}(G^{\prime \prime },p)\right|$, certifying that it is very unlikely for any vertex in $\mathrm{R}(G^{\prime \prime },P^{\prime \prime })$ to be sampled as a pivot. This yields the $n^{0.136}$-shortcut set in near-linear time for dense graphs.

Finally, we parallelize the shortcut set construction by using a blackbox framework provided by [9]. Morally, the framework says that (up to some fudging) we need only guarantee that a parallel algorithm for computing a $\beta$-shortcut set runs in $\tilde{O}(\beta )$ span on DAGs with reachability hopbound $\tilde{O}(\beta )$; this is enough to show that a $\beta$-shortcut set runs in $\tilde{O}(\beta )$ span on any digraph, regardless of its diameter. It is easy to show that our sequential construction for $\beta$-shortcut sets run in $\beta$ span on DAGs with reachability hopbound $\tilde{O}(\beta )$, since BFS calls will run in span $\beta$.

The way the diameter of the shortcut set is upper bounded comes from [8]. There, an arbitrary path $P$ is selected for the sake of analysis. Notice first that $P$ is split into contiguous subpaths in the recursive calls and the same is true of its subpaths, and so on. More specifically, observe the following (shown in [11]).

[11] shows that the subproblem tree of any path $P$ has at most $n^{1/2+O(1/\log k)}$ nodes. We employ algorithmic tactics to prune away nodes from this tree in our analysis, to the extent that the tree we analyze has a substantially smaller number of nodes. For example, a node $P^{\prime }$ in recursive instance $G^{\prime }$ may have a large subtree in $P$’s subproblem tree. If we are able to identify some structure in $G^{\prime }$ so that $P^{\prime }$ is immediately shortcutted to $O(1)$ hops, we are then permitted to ignore the subtree rooted at $P^{\prime }$ in our analysis.

In view of this, we will use a pruning strategy (called TC-Pruning) which prunes away all nodes $P^{\prime }$ where $\left|\mathrm{R}(G^{\prime },P^{\prime })\right|$ is small. Using our new analysis of the diameter of the JLS shortcut set, we will be able to say that the number of nodes $P^{\prime }$ where $\left|\mathrm{R}(G^{\prime },p^{\prime })\right|$ is large is much less than $n^{1/2+O(1/\log k)}$, which yields our improvement. See Section 4.2 for details.

We close this subsection with the following crucial lemma from [11] which says that the size of balls around vertices are exponentially decreasing in $r$, the recursion level.

We omit rewriting a formal proof of Proposition 9, but this follows from a simple induction on the recursion level: if $\left|R^{-}(G^{\prime },v)\right|\le n{k}^{-r}$ at level $r-1$, then it is true also for level $r$ and, otherwise, one of the first $n{k}^{-r}$ ancestors of $v$ (say $p$) will be sampled as a pivot with high probability, precluding any of the later ancestors from being retained in $R^{-}(G^{\prime },v)$ at level $r$ since they receive the label “I have no relation to $p$” while $v$ receives the label “$p$ reaches me”.