Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication

Consider an $n$-vertex directed graph $G=(V,E)$ and a pair of vertices $u,v\in V$. We say that $v$ is reachable from $u$ (denoted $u\leadsto v$) iff there exists a directed path in $G$ that starts at $u$ and ends in $v$. Given a subset $S\subseteq V$ of $n^{\sigma}$ designated vertices called sources, for some $0\leq\sigma\leq 1$, the $S\times V$-reachability matrix $R=R(S,V)$ is a rectangular Boolean matrix of dimension $n^{\sigma}\times n$, in which for every pair $(s,v)\in S\times V$, the respective entry $R[s,v]$ is equal to $1$ iff $v$ is reachable from $s$ in $G$. The $S\times V$-direachability problem is, given a directed graph $G=(V,E)$, and a subset $S\subseteq V$ of sources, to compute the reachability matrix $R(S,V)$.

To the best of our knowledge, despite the fundamental nature of this problem, it was not explicitly studied so far. There are two existing obvious solutions for it. The first one runs a BFS (or DFS) from every source $s\in S$, and as a result requires $O(m\cdot n^{\sigma})$ time. We call this algorithm BFS-based. For dense graphs this running time may be as large as $O(n^{2+\sigma})$. The second solution (which we call TC-based) uses fast square matrix multiplication to compute the transitive closure $TC(G)$ in $\tilde{O}(n^{\omega})$ time, where $\omega\leq 2.371552\ldots$ is the matrix multiplication exponent. The upper bound $\omega\leq 2.371552\ldots$ is due to [WXXZ24] (see also [Gal24, GU18, LG14, CW90]).¹¹1The expression $O(n^{\omega})$ is the running time of the state-of-the-art algorithm for computing a matrix product of two square matrices of dimensions $n\times n$.

In this paper we employ recent breakthroughs due to Kogan and Parter [KP22b, KP22a] concerning directed shortcuts, and devise an algorithm that outperforms the two existing solutions (BFS-based and TC-based) for computing $S\times V$-reachability matrix whenever $\tilde{\sigma}\leq\sigma\leq 0.53$. (Recall that $\sigma=\log_{n}|S|$. Here $1/3<\tilde{\sigma}<0.3336$ is a universal constant.) The running time of our algorithm is $\tilde{O}(n^{1+\tiny{\frac{2}{3}}\omega(\sigma)})$, where $\omega(\sigma)$ is rectangular matrix multiplication exponent, i.e., $O(n^{\omega(\sigma)})$ is the running time of the state-of-the-art algorithm for multiplying a rectangular matrix with dimensions $n^{\sigma}\times n$ by a square matrix of dimensions $n\times n$. See Table 1 for the values of this exponent (due to [WXXZ24]), and Table 2 for the comparison of running time of our algorithm with that of previous algorithms for $S\times V$-direachability problem in the range $\tilde{\sigma}\leq\sigma\leq 0.53$ (in which we improve the previous state-of-the-art). The largest gap between our exponent and the previous state-of-the-art is for $0.37\leq\sigma\leq 0.38$. Specifically, our exponent for $\sigma=0.38$ is $2.33751$, while the state-of-the-art is $2.371552$.

Moreover, we show that our algorithm improves the state-of-the-art solutions for $S\times V$-direachability problem in a much wider range of $\sigma$ on sparser graphs. Specifically, we show that for every $\tilde{\sigma}\leq\sigma<1$, there exists a non-empty interval $I_{\sigma}\subset[1,2]$ of values $\mu$, so that for all input graphs with $m=\Theta(n^{\mu})$ edges, our algorithm outperforms both the BFS-based and TC-based solutions. The running time of our algorithm on such graphs is $\tilde{O}(n^{\tiny{\frac{1+\mu+2\cdot\omega(\sigma)}{3}}})$.

We provide some sample values of these intervals in Table 4. See also Table 5 for the comparison between our new bounds for $S\times V$-direachability on sparser graphs and the state-of-the-art ones. For example, for $\sigma=0.5$ (when $|S|=\sqrt{n}$), the interval is $I_{\sigma}=(1.793,2]$, i.e., our algorithm improves the state-of-the-art solutions as long as $\mu>1.793$. Specifically, when $\mu=1.9$, our algorithm requires $\tilde{O}(n^{2.3287\ldots})$ time for computing reachability from $\sqrt{n}$ sources, while the state-of-the art solution is the TC-based one, and it requires $\tilde{O}(n^{2.371552\ldots})$ time. Another example is when $\sigma=0.6$. The interval $I_{\sigma}=I_{0.6}$ is $(1.693,1.93)$, and for $\mu=1.75$ our solution requires $\tilde{O}(n^{2.312\ldots})$ time, while the state-of-the-art BFS-based solution requires $O(n^{2.35})$ time.

We also devise a recursive variant of our algorithm that further improves our bounds conditioned on a certain algorithmic assumption. Specifically, we define the directed reachability problem with parameters $n^{\sigma}$ and $n^{\delta}$ denoted $DR(n^{\sigma},n^{\delta})$, for a pair of parameters $0\leq\sigma,\delta\leq 1$. The parameter $\sigma$ is $\log_{n}|S|$ as above. The parameter $\delta$ affects the hop-bound $D=n^{\delta}$. The problem $DR(n^{\sigma},n^{\delta})$ accepts as input an $n$-vertex graph $G=(V,E)$ and a set $S$ of $n^{\sigma}$ sources, and asks to compute, for every $s\in S$, the set $\mathcal{V}_{s}$ of vertices reachable from $s$ in at most $n^{\delta}$ hops. For a problem $\Pi$, we denote by $\mathcal{T}(\Pi)$ its time complexity. In particular $\mathcal{T}(DR(n^{\sigma},n^{\delta}))$ stands for time complexity of $DR(n^{\sigma},n^{\delta})$. Observe that $DR(n^{\sigma},n^{\delta})$ can be easily solved by $n^{\delta}$ rectangular Boolean matrix products of an $n^{\sigma}\times n$ matrix by an $n\times n$ square matrix. Let $A=A(G)$ be the adjacency matrix of the input graph $G$. In the first iteration, the rectangular matrix $B$ is just the matrix $A$ restricted to $n^{\sigma}$ rows that correspond to sources $S$, while the square matrix $A^{\prime}$ is the adjacency matrix $A$ augmented with a self-loop for every vertex. On the next iteration $B$ is replaced by the Boolean matrix product $B\star A^{\prime}$, etc. This process continues for $n^{\delta}$ iterations. Thus, $\mathcal{T}(DR(n^{\sigma},n^{\delta}))=O(n^{\omega(\sigma)+\delta})$. Now consider the following paths directed reachability problem, $PDR(n^{\sigma},n^{\delta})$, in which instead of $n^{\sigma}$ designated source vertices we are given $n^{\sigma}$ dipaths $\mathcal{P}=\{p_{1},p_{2},\ldots,p_{n^{\sigma}}\}$. For every path $p\in\mathcal{P}$, and every vertex $u\in V$, we want to compute if $u$ is reachable from some vertex $v\in V(p)$ in at most $n^{\delta}$ hops, and if it is the case, we want to output the last vertex $v_{p}(u)$ on $p$ from which $u$ is reachable within at most $n^{\delta}$ hops.

Interestingly, the BFS-based algorithm for $DR(n^{\sigma},n^{\delta})$ problem applies (with slight modifications) to the $PDR(n^{\sigma},n^{\delta})$ problem, providing a solution with running time $O(n^{\mu+\sigma})$ (like for the $DR(n^{\sigma},n^{\delta})$ problem) [KP22a]. On the other hand, it does not seem to be the case for the algorithm with running time $O(n^{\omega(\sigma)+\delta})$ time for $DR(n^{\sigma},n^{\delta})$ that we described above. Our assumption, which we call paths direachability assumption, is that one nevertheless can achieve running time $\tilde{O}(n^{\omega(\sigma)+\delta})$ for $PDR(n^{\sigma},n^{\delta})$ problem as well.

We show that under this assumption a variant of our algorithm improves the state-of-the-art $S\times V$-reachability algorithms for dense graphs ($\mu=2$) for all values of $\tilde{\sigma}\leq\sigma<1$ (and not just in the range $\tilde{\sigma}\leq\sigma\leq 0.53$, which we show unconditionally). Recall that $1/3<\tilde{\sigma}<0.3336$ is a universal constant.

We analyse a sequence of algorithms $\mathcal{A}_{0},\mathcal{A}_{1},\mathcal{A}_{2},\ldots$. For each algorithm $\mathcal{A}_{i}$, $i=0,1,2,\ldots$, we consider the threshold value $\sigma_{i}<1$ upto which this algorithm outperforms the existing state-of-the-art solutions. We show that $0.53\leq\sigma_{0}<\sigma_{1}<\ldots<\sigma_{i}<\sigma_{i+1}<\ldots\leq 1$, and that $\lim_{i\to\infty}\sigma_{i}=1$. In other words, for any exponent $\sigma<1$ of the number of sources, there exists a (sufficiently large) index $i$ such that the algorithm $\mathcal{A}_{i}$ outperforms existing state-of-the-art solutions for the $S\times V$-direachability problem with $|S|=n^{\sigma}$.

We also identify some additional assumptions under which the paths direachability assumption holds. In particular, consider the max-min matrix product. Given two matrices $B$ and $A$ of appropriate dimensions (so that matrix product $B\cdot A$ is defined), max-min product $C=B\ovee A$ is defined as follows: for indices $i,j$ so that $i$ is an index of a row of $B$ and $j$ is an index of a column of $A$, we have $C[i,j]=\max_{k}\min\{B[i,k],A[k,j]\}$, where $k$ ranges over all possible indices of columns of $B$.

We show that $PDR(n^{\sigma},n^{\delta})$ problem reduces to $n^{\delta}$ invocations of the max-min matrix products for matrices of dimensions $n^{\sigma}\times n$ and $n\times n$. Thus, assuming that such a product can be computed in $\tilde{O}(n^{\omega(\sigma)})$ time implies paths direachability assumption. We refer to this assumption as max-min product assumption. Max-min matrix product was studied in [DP09] and [GIA⁺21]. However, current state-of-the-art bounds for it are far from the desired bound of $\tilde{O}(n^{\omega(\sigma)})$.

Admittedly, it is not clear how likely are these assumptions. We find it to be an intriguing direction for future research. Also, we believe that the analysis of our algorithms under these assumptions is of independent interest, and that it sheds light on the complexity of multi-source reachability problem. Furthermore, getting sufficiently close to the running time of $\tilde{O}(n^{\omega(\sigma)+\delta})$ for paths direachability assumption or to $\tilde{O}(n^{\omega(\sigma)})$ for the max-min product assumption would suffice for providing further improvements to the state-of-the-art bounds for this fundamental problem.

In this section we provide a high-level overview of our algorithms. Given a digraph $G=(V,E)$, and a positive integer parameter $D$, we say that a graph $G^{\prime}=(V,H)$ is a $D$-shortcut of $G$ if for any ordered pair $u,v\in V$ of vertices, $v$ is reachable from $u$ in $G$ iff it is reachable from $u$ in $G\cup G^{\prime}=(V,E\cup H)$ using at most $D$ hops. Kogan and Parter [KP22b, KP22a] showed that for any parameter $1\leq D\leq\sqrt{n}$, for any digraph $G$, there exists a $D$-shortcut $G^{\prime}$ with $\tilde{O}(\tiny{\frac{n^{2}}{D^{3}}}+n)$ edges, and moreover, this shortcut can be constructed in $\tilde{O}(m\cdot n/D^{2}+n^{3/2})$ time [KP22a].

Our first algorithm starts with invoking the algorithm of [KP22a] for an appropriate parameter $D$. We call this the diameter-reduction step of our algorithm. We then build two matrices. The first one is the adjacency matrix $A^{\prime}$ of the graph $G\cup G^{\prime}$, with all the diagonal entries equal to $1$. This is a square $n\times n$ matrix, and the diagonal entries correspond to self-loops. The second matrix $B$ is a rectangular $|S|\times n$ matrix. It is just the adjacency matrix of of the graph $G\cup G^{\prime}$ restricted to $|S|$ rows corresponding to designated sources of $S$.

Next, our algorithm computes the Boolean matrix product $B\star A^{\prime D}$. Specifically, the algorithm computes the product $B\star A^{\prime}$, and then multiplies it by $A^{\prime}$, etc., and does so $D$ times. Hence, this computation reduces to $D$ Boolean matrix products of a rectangular matrix of dimensions $|S|\times n$ by a square matrix with dimensions $n\times n$. Each of these $D$ Boolean matrix products can be computed using standard matrix multiplication (see Section 2.1). We use fast rectangular matrix multiplication algorithm by [WXXZ24] to compute these products. As $|S|=n^{\sigma}$, this computation, henceforth referred to as the reachability computation step, requires $O(D\cdot n^{\omega(\sigma)})$ time.

Observe that the running time of the reachability computation step grows with $D$, and the running time of the diameter-reduction step decreases with $D$. It is now left to balance these two running times by carefully choosing $D$. This completes the overview of our basic direachability algorithm, that improves (unconditionally) the state-of-the-art running time for $S\times V$-direachability, $|S|=n^{\sigma}$, for $\tilde{\sigma}\leq\sigma\leq 0.53$, $\tilde{\sigma}<0.3336$. Moreover, as was mentioned above, for any $\sigma$, $\tilde{\sigma}\leq\sigma<1$, there is a non-empty interval $I_{\sigma}\subseteq[1,2]$ of values $\mu$, such that thus algorithm improves (also, unconditionally) upon state-of-the-art solutions for this problem on graphs with $m=\Theta(n^{\mu})$ edges,

To improve these results further (based on the paths direachability assumption), we observe that the algorithm of Kogan and Parter [KP22a] for building shortcuts has two parts. In the first part it computes a subset $P^{\prime}$ of $\tilde{O}(n/D^{2})$ dipaths and a subset $V^{\prime}$ of $\tilde{O}(n/D)$ vertices. This step is implemented via a reduction to a min-cost max-flow (MCMF) instance. Using the recent advances in this area [CKL⁺22], it can be done within $\tilde{O}(m^{1+o(1)}+n^{3/2})$ time. The second part of the algorithm of [KP22a] involves computing reachabilities between all pairs $(p,v)\in P^{\prime}\times V^{\prime}$. Here for every pair $(p,v)\in P^{\prime}\times V^{\prime}$, one needs to compute the last (if any) vertex on $p$ from which $v$ is reachable. Under our paths direachability assumption, this second part can be implemented via a recursive invocation of our $S\times V$-reachability algorithm. Our conditional bounds are achieved by analysing this recursive scheme.

Related Work Fast rectangular matrix multiplication in conjunction with hopsets was recently employed in a similar way in the context of distance computation in undirected graphs by Elkin and Neiman [EN22]. Directed hopsets, based on Kogan-Parter constructions of shortcuts [KP22b, KP22a], were recently devised in [BW23].

Recall that for a fixed integer $n$ and $0<\sigma<1$, $\omega(\sigma)$ denotes the exponent of $n$ in the number of algebraic operations required to compute the product of an $n^{\sigma}\times n$ matrix by an $n\times n$ matrix. Let $B$ be an $n^{\sigma}\times n$ Boolean matrix (i.e., each entry of $B$ is either $0$ or $1$.). Let $A$ be another Boolean matrix of dimensions $n\times n$. Define the Boolean matrix product $C=B\star A$ by

$$C[i,j]=\small{\bigvee_{1\leq k\leq n}}B[i,k]\wedge A[k,j],$$

(1)

where $\vee$ and $\wedge$ stand for binary operations $OR$ and $AND$ respectively.

Note that the Boolean matrix product (BMM henceforth) of $B$ and $A$ can be easily computed by treating the two matrices as standard integer matrices and computing the integer matrix product $\tilde{C}=B\cdot A$ over the integers, and then setting $C[i,j]=1$ if $\tilde{C}[i,j]\geq 1$. Thus the number of operations required to compute the BMM of $B$ and $A$ as above is $O(n^{\omega{(\sigma)}})$. Vassilevska Williams et al. presented the current state-of-the-art upper bounds on $\omega(\sigma)$ (Table 1 of [WXXZ24]). We present these bounds in Table 1 here for completeness.)

In this section, we consider general $n$-vertex, $m$-edge digraphs, i.e., $m$ may be as large as $n(n-1)$. In the next section, we analyse the case of sparser graphs, and show that when $m=\Theta(n^{\mu})$, for some $\mu<2$, our bounds can be further improved.

Let $D=n^{\delta}$ for some $0<\delta\leq 1/2$. In the diameter reduction step we compute a $D$-shortcut of $G$. By Theorem 1, this can be done in time $\mathcal{T}_{DR}=\tilde{O}(m\cdot n/D^{2}+n^{3/2})=\tilde{O}(n^{3-2\delta})$. In the reachability computation step we perform $D=n^{\delta}$ iterations, each of which computes a rectangular matrix product of an $n^{\sigma}\times n$ matrix by an $n\times n$ matrix. Each matrix product requires $O(n^{\omega(\sigma)})$ time. It follows that $\mathcal{T}_{RC}=O(n^{\omega(\sigma)+\delta})$. The overall time complexity of the algorithm is therefore $\mathcal{T}_{DR}+\mathcal{T}_{RC}=\tilde{O}(n^{3-2\delta}+n^{\omega(\sigma)+\delta})$. Let $g_{0}(\sigma)$ denote the exponent of $n$ (as a function of $\sigma$) in the overall time complexity of our algorithm. It follows that

$$g_{0}(\sigma)=\min_{\delta}\max\{3-2\delta,\omega(\sigma)+\delta\}.$$

(2)

Since $3-2\delta$ decreases when $\delta$ grows and $\omega(\sigma)+\delta$ grows, the minimum is achieved when the following equation holds

$\displaystyle\begin{aligned} 3-2\delta&=\omega(\sigma)+\delta\text{, i.e.,}\\ \delta&=1-\frac{1}{3}\cdot\omega(\sigma).\end{aligned}$

(3)

The parameter $D$ is therefore set as $D=n^{\delta}$, with $\delta$ given by Equation (3). It follows from (2) and (3) that

$$g_{0}(\sigma)=1+\frac{2}{3}\cdot\omega(\sigma).$$

(4)

Recall that the time complexity $\mathcal{T}_{Naive}$ of the naive algorithm is given by $\mathcal{T}_{Naive}=O(m\cdot|S|)=O(n^{2+\sigma})$. Hence in the range $\omega-2=0.371552\leq\sigma\leq 1$, the naive algorithm is no better than computing the transitive closure of the input digraph. The latter requires $\tilde{O}(n^{\omega})$ time (where $\omega=\omega(1))$. For our algorithm to do better than the naive algorithm in this range we require

$$1+\frac{2}{3}\cdot\omega(\sigma)<\omega.$$

Incorporating the state-of-the-art upper bounds on $\omega(\sigma)$ from Table 1, we get that $g_{0}(\sigma)<\omega$, for $\sigma\leq 0.53$. Therefore, since $\omega(\cdot)$ is a monotone function, our algorithm can compute $S\times V$-direachability in $o(n^{\omega})$ time for $1\leq|S|\leq n^{0.53}$ sources, as opposed to naive algorithm that can only do so for $1\leq|S|\leq n^{\omega-2}$ .

Moreover, for $0.335\leq\sigma<0.371552$, $g_{0}(\sigma)=1+\frac{2}{3}\omega(\sigma)<2+\sigma$. Observe that by convexity of $\omega(\sigma)$, it suffices to verify the inequality for the endpoints $\sigma=0.335$ and $\sigma=0.371552$. Therefore in the range $n^{0.335}\leq|S|<n^{0.53}$, our algorithm outperforms the state-of-the-art solutions.

Denote by $\tilde{\sigma}$ the threshold value such that

$$g_{0}(\tilde{\sigma})=1+\frac{2}{3}\omega(\tilde{\sigma})=2+\tilde{\sigma}.$$

(5)

For all $\tilde{\sigma}<\sigma<1$, we have

$$g_{0}(\sigma)<2+\sigma.$$

(6)

As the Inequality (6) holds for $\sigma=0.335$, it follows that $1/3<\tilde{\sigma}<0.335$. (The Inequality (6) does not hold for $\sigma=1/3$.) In fact, in Section 3.2 (between Lemma 1 and Lemma 2) we argue that $\tilde{\sigma}<0.3336$. We conclude with the following theorem:

For example, we compute $S\times V$-direachability for $S=n^{\sigma}$, $\sigma=0.4$ in time $O(n^{g_{0}(0.4)})=O(n^{2.33969})$, improving upon the state-of-the-art bound of $O(n^{2.4})$ for naive algorithm and the state-of-the-art bound of $\tilde{O}(n^{2.371552})$ obtained by fast square matrix multiplication. In Table 2, we present values of $g_{0}(\sigma)$ corresponding to some specific values of $\sigma$ in the range $[\tilde{\sigma},0.53]$ and show how they compare to the exponent of $n$ in $S\times V$-naiveReach (see Definition 1) and $S\times V$-squareReach (see Definition 2).

In this section we argue that when our input $n$-vertex $m$-edge digraph $G$ has $m=\Theta(n^{\mu})$ edges, for some $\mu<2$, then our bounds from Theorem 2 can be further improved. Let $m=\Theta(n^{\mu})$ be the size of the edge set of $G$, where $0\leq\mu<2$. As before, let $D=n^{\delta}$, for $0<\delta\leq 1/2$. Applying Theorem 1 for $m=\Theta(n^{\mu})$ and $D=n^{\delta}$, it follows that $\mathcal{T}_{DR}=\tilde{O}(n^{1+\mu-2\delta}+n^{3/2})$. Recall that the running time of the reachability computation step is $\mathcal{T}_{RC}=O(n^{\omega(\sigma)+\delta})$. The second term of $\mathcal{T}_{DR}$ will always be dominated by $\mathcal{T}_{RC}$. The overall time complexity of the algorithm is therefore $\mathcal{T}_{DR}+\mathcal{T}_{RC}=\tilde{O}(n^{1+\mu-2\delta}+n^{\omega(\sigma)+\delta})$. Let $g^{(\mu)}_{0}(\sigma)$ denote the exponent of $n$ (as a function of $\sigma$) in the overall time time complexity of our algorithm. It follows that

$$g^{(\mu)}_{0}(\sigma)=\min_{\delta}\max\{1+\mu-2\delta,\omega(\sigma)+\delta\}.$$

(7)

This expression is minimized when

$\displaystyle\begin{aligned} 1+\mu-2\delta&=\omega(\sigma)+\delta\text{, i.e.,}\\ \delta&=\frac{1+\mu-\omega(\sigma)}{3}.\end{aligned}$

(8)

It follows from (7) and (8) that

$$g^{(\mu)}_{0}(\sigma)=\frac{1+\mu+2\omega(\sigma)}{3}.$$

(9)

Note that for $\mu=2$, we have $g^{(\mu)}_{0}(\sigma)=g_{0}(\sigma)$. Also, when $\mu<2$, the exponent $g^{(\mu)}_{0}(\sigma)$ is smaller than $\omega$ for a wider range of $\sigma$ than the exponent $g_{0}(\sigma)$. On the other hand the sparsity of the input digraph also improves the time complexity $\mathcal{T}_{Naive}=O(m\cdot n^{\sigma})=O(n^{\mu+\sigma})$ of the naive algorithm. It is possible that for a given combination of $\sigma$ and $\mu$, $\mathcal{T}_{Naive}$ may be better than the time complexity, $\tilde{O}(n^{\frac{1+\mu+2\omega(\sigma)}{3}})$, of our algorithm. For our algorithm to outperform the naive algorithm, we need

$$\frac{1+\mu+2\omega(\sigma)}{3}<\mu+\sigma.$$

This condition is equivalent to

$$\mu>\omega(\sigma)+\frac{1}{2}-\frac{3}{2}\sigma.$$

(10)

By substituting values of $\omega(\sigma)$ from Table 1 for specific values of $\sigma$, we get corresponding lower bounds on $\mu$. In Table 3, we present these lower bounds for various values of $\sigma$.

For our algorithm to work in $o(n^{\omega})$ time, we need

$$\frac{1+\mu+2\omega(\sigma)}{3}<\omega\text{, i.e.,~{}}\mu<3\omega-2\omega(\sigma)-1.$$

(11)

For $\sigma=1$, Inequality (11) implies that $\mu<\omega-1$, matching the lower bound $\mu>\omega-1$ implied by (10). Indeed, our algorithm improves existing bounds only for $\sigma<1$. For every $\sigma<1$, we get some non-trivial intervals $I_{\sigma}$ of $\mu$ for which $g^{(\mu)}_{0}(\sigma)<\min\{\mu+\sigma,\omega\}$. For example, for $\sigma=0.5$, $\mu>1.793$ (see Table 3) ensures that $g^{(\mu)}_{0}(\sigma)<\mu+\sigma$. For inequality $g^{(\mu)}_{0}(\sigma)<\omega$ to hold, substituting $\sigma=0.5$ in (11) implies that $\mu<2.028668$. It follows that the inequality always holds for all $\mu$, i.e., the condition on $\mu$ for $\sigma=0.5$ is that $\mu>1.793$. We computed these values of intervals for various values of $\sigma$. Specifically, for a number of values of $\sigma$, using the best known upper bounds on $\omega(\sigma)$, we numerically computed the intervals $I_{\sigma}=(\mu_{1},\mu_{2})$, such that for graphs with $m=\Theta(n^{\mu})$ edges, $\mu_{1}<\mu<\mu_{2}$, our algorithm improves the existing bounds bounds on the $S\times V$-direachability problem. In Table 4, we present these intervals for various values of $\sigma$.

These results suggest that for all $\sigma,\tilde{\sigma}<\sigma<1$, there is a non-empty interval of $\mu$ such that for digraphs with $m=\Theta(n^{\mu})$ edges, our algorithm improves over existing bounds for $S\times V$-direachability for $|S|=n^{\sigma}$. We will soon prove it formally.

In Table 5, we present a comparison of our algorithm for graphs with $m=\Theta(n^{\mu})$ edges for various combinations of $\mu$ and $\sigma$.

Recall that $\frac{1}{2}+\omega(\sigma)-\frac{3}{2}\sigma$ is the lower bound on the value of $\mu$ implied by Inequality (10), i.e., for $\mu>1/2+\omega(\sigma)-3/2\sigma$, our algorithm is better than the $S\times V$-naiveReach method. The threshold $\tilde{\sigma}$ is the value such that $\frac{1}{2}+\omega(\sigma)-\frac{3}{2}\sigma=2$, i.e., $\omega(\tilde{\sigma})=\frac{3}{2}(1+\tilde{\sigma})$ holds. (Recall that we defined it in Section 3.1 as the value that satisfies $1+\frac{2}{3}\omega(\tilde{\sigma})=2+\tilde{\sigma}$. These two conditions are equivalent.)

To evaluate the value of $\tilde{\sigma}$ we note that for $\sigma=0.34$, we have $\omega(\sigma)=2.0006$ (see Table 1) and $\frac{3}{2}(1+\sigma)=2.01$. For $\sigma=1$, we have $\omega(\sigma)=2.371552$ and $\frac{3}{2}(1+\sigma)=3$. Thus $\omega(\sigma)<\frac{3}{2}(1+\sigma)$ holds for $\sigma=0.34$ and for $\sigma=1$. By convexity of the function $\omega(\sigma)$, it follows that this inequality holds for all $0.34\leq\sigma\leq 1$. However, for $\sigma=1/3$, $\omega(\sigma)>\omega(0.33)>2.0001>2$, whereas $\frac{3}{2}(1+\sigma)=2$. Therefore, there exists a constant $\tilde{\sigma}$, $1/3<\sigma_{0}<0.34$ (satisfying $\omega(\tilde{\sigma})=\frac{3}{2}(1+\tilde{\sigma})$), such that the inequality $\omega(\sigma)<\frac{3}{2}(1+\sigma)$ (and thus $g_{0}(\sigma)>\omega(\sigma)+\frac{1-\sigma}{2}$) holds for $\tilde{\sigma}<\sigma\leq 1$. In fact, one can verify that $1/3<\tilde{\sigma}<0.3336$, as $\omega(0.3336)<2.00028$, while $\frac{3}{2}(1+0.3336)=2.0004$. In the following lemma we formally prove that for $\tilde{\sigma}<\sigma<1$, the intervals $I_{\sigma}$ are non-empty.