Constructing Long Paths in Graph Streams

We will first explain the key ideas behind our algorithm. As observed by Karger et al. [23], a path of length $d_{\text{min}}$, where $d_{\text{min}}$ is the minimum degree of the input graph $G$, can be computed as follows: Start at any vertex $v_0$ and visit an arbitrary neighbor that we denote by $v_1$. In a general step $i$, we have already constructed the path $v_0,\mathrm{\dots },v_i$. We then visit a neighbor $v_{i+1}$ of $v_i$ that has not previously been visited. Then, as long as , we can always find a yet unvisited neighbor, and, hence, we obtain a path of length $d_{\text{min}}$. We first see that this argument can also be applied to the average degree $d$ of the graph $G$. It is well known that, by repeatedly removing vertices of degree at most $d/2$ from $G$ until no such vertex remains, we are left with a non-empty graph $G^{\prime }$ with min-degree at least $d/2$. We can now apply the same argument as above to $G^{\prime }$ and thus find a path of length at least $d/2$.

The approach outlined above, however, does not yield a small space streaming algorithm since a) we do not know which vertices are contained in $G^{\prime }$, and b) we cannot afford to store $\mathrm{\Theta }(d)$ incident edges on each vertex. To overcome these obstacles, we resort to randomization. Our algorithm solely samples $O(n\log n)$ random edges $F$ from the input graph and outputs a longest path among the edges $F$. To see that a long path in $F$ exists, we argue that the subset of edges $F^{\prime }\subseteq F$ that are also contained in $G^{\prime }$ contains a path of length at least $d/3$ with high probability. Such a path can be constructed greedily. Suppose we have already constructed a partial path of length solely using the edges $F^{\prime }$, and let $v_{\mathrm{\ell }+1}\in V(G^{\prime })$ denote its current endpoint. Then, since $v_{\mathrm{\ell }+1}$ has a degree of at least $d/2$ in $G^{\prime }$, there are at least $d/2-d/3=d/6$ neighbors of $v_{\mathrm{\ell }+1}$ in $G^{\prime }$ that have not yet been visited in the path. Since we sample $\mathrm{\Theta }(n\log n)$ edges overall, the probability that any one of these edges incident to $v_{\mathrm{\ell }+1}$ that connect to these $d/6$ vertices is sampled is $\mathrm{\Omega }(\frac{n\cdot \log n}{n\cdot d})=\mathrm{\Omega }(\frac{\log n}{d})$, which implies that at least one of these edges is sampled with high probability and we can extend the path.

All our space lower bounds are proved in the one-way two-party communication setting. In this setting, two parties that we denote by Alice and Bob each hold a subset of the edges of the input graph $G=(V,E=E_A\cup E_B)$, with $E_A$ being Alice’s edges, and $E_B$ being Bob’s edges. Alice sends a single messages $\mathrm{\Pi }$ to Bob, and Bob computes the output of the protocol. Then, it is well-known that a lower bound on the size of the message $\mathrm{\Pi }$ also constitutes a lower bound on the space of any one-pass streaming algorithm.

We work with induced matchings in all our lower bound constructions. In a graph $G=(V,E)$, a matching $M\subseteq E$ is induced if the edges of the vertex-induced subgraph $G[V(M)]$ are precisely the edges of $M$. Suppose now that $G$ is bipartite, and we denote it by $G=(A,B,E=E_A\cup E_B)$. Furthermore, we suppose that Alice’s subgraph, i.e., the graph spanned by the edges $E_A$, contains a matching $M$ that is induced in the final graph. We say that $M$ is the special matching. We complete our lower bound constructions so that:

1. 1.

   Every long path in the graph must contain many edges of the special matching $M$;

2. 2.

   The special matching $M$ is hidden among the edge set $E_A$ so that Alice cannot identify $M$, and, given a limited communication budget, Alice therefore cannot forward many of $M$’s edges to Bob.

The two properties then imply a lower bound since, if Bob knows only few edges of $M$, but every long path contains many such edges, then Bob cannot output a long path.

To achieve property $2$, in our insertion-deletion lower bound, we make use of edge deletions as part of Bob’s input to turn a large matching in $E_A$ into an induced matching, and in our insertion-only lower bounds, we work with Rusza-Szemerédi graphs (RS-graphs in short), which have been extensively used for proving lower bounds for matching problems in the streaming setting (e.g., [18, 8, 26, 27]). An $(r,t)$-RS-graph is a balanced bipartite graph on $2n$ vertices such that its edge set can be partitioned into $t$ induced matchings $M_1,\mathrm{\dots },M_t$, each of size $r$. Our insertion-only constructions are such that each of these $t$ matchings can take the role of the special matching $M$, which will allow us to argue that Alice essentially has to send many edges of each induced matching to Bob if Bob is to report a long path. We note that the framework of working with RS-graphs and a special hidden matching among Alice’s edges is well-established and has previously been used, for example, in [18, 7, 3, 27, 5, 4].

Regarding establishing property $1$, we pursue different strategies that depend on the specific streaming setting, and on whether we work with directed or undirected graphs. These strategies are described below and illustrated in Figure 1.

Directed Graphs in the Insertion-only Model. The cleanest case is our lower bound for directed graphs. In this setting, Alice holds the edges of an RS-graph $G^{\prime }=(A,B,E)$, and we assume that all edges are directed from $A$ to $B$. We then pick a matching $M_J$, for a uniform random $J\in [t]$, and Bob inserts a random matching $N$ that matches $B(M_J)$ to $A(M_J)$ so that all edges in $N$ are directed from $B$ to $A$. We then leverage the well-known result that the expected length of a longest cycle in a random permutation of the set $[r]$ is of length $\mathrm{\Theta }(r)$ [20, 19] in order to argue that $M_J\cup N$ contains a path of expected length $\mathrm{\Theta }(|M_J|)$. It then remains to argue that every path of length $\mathrm{\ell }$, for any $\mathrm{\ell }$, in the input graph $G=G^{\prime }\cup N$ must contain $\mathrm{\Omega }(\mathrm{\ell })$ edges of $M_J$, which uses the fact that the matching $M_J$ is induced. Since, however, Alice did not know that $M_J$ is the special matching, Alice is required to send a large number of edges of each induced matching to Bob so that Bob can output a long path.

For technical reasons, our graph construction is slightly more involved than described above since we need to turn Alice’s RS-graph into an input distribution, see Section 4 for details. While it is easy to argue that if Alice sends $k$ edges of $M_J$ to Bob then Bob can compute a path of length at most $O(k)$ in $M_J\cup N$, we need to argue a much stronger bound. We show that, even if Alice sends as many as $r/100$ $M_J$ edges to Bob then Bob can still only find a path of size $O(\log r)$ in $M_J\cup N$. We implement our approach using the information complexity paradigm, including direct sum and message compression arguments.

Undirected Graphs in the Insertion-only Model. In our construction for undirected graphs, Alice holds an RS-graph $G^{\prime }=(A,B,E)$, and, given a random index $J\in [t]$, Bob holds a random matching $N$ matching $A(M_J)$ to $B(M_J)$. Similar as above, the matchings $M_J\cup N$ contain a path of length $\mathrm{\Omega }(|M_J|)$. However, it is no longer true that any long path in $G^{\prime }\cup N$ must contain many edges of $M_J$ as, for example, the vertices in $V\setminus V(M_J)$ can now be used to visit the vertices within $V(M_J)$ as their incident edges are undirected.

Our aim is to ensure that it is detrimental for constructing long paths to include many edges across the cut $(V\setminus V(M_J),V(M_J))$ in the path. Once this property is established, we will argue that, if Bob only knows few of the $M_J$ edges then many vertices of $V(M_J)$ will remain unvisited in the output path, which implies that the path is bounded in length as not all vertices are visited. To argue that only few edges across the cut $(V\setminus V(M_J),V(M_J))$ are included in the output path, we ensure that all the vertices $v\in V\setminus V(M_J)$ serve as gateways to other parts of the graph that are introduced by Bob. The construction is so that these other parts cannot be visited if $v$ connects to a vertex in $V(M_J)$ in the output path, which will then be detrimental for the construction of a long path. To achieve this, Bob introduces additional edges as follows. First, let ${𝒫}^{\prime }$ be a path consisting of novel edges that visits every vertex in $V\setminus V(M_J)$, and let $𝒫$ be the path obtained from ${𝒫}^{\prime }$ by subdividing every edge in ${𝒫}^{\prime }$, $\mathrm{\ell }$ times, for some integer $\mathrm{\ell }$. Furthermore, this path is connected to the longest path within $M_J\cup N$. Then, the path $𝒫$ significantly contributes to the longest path in the input graph. Observe, however, if a vertex $v\in V\setminus V(M_J)$ connects to a vertex in $V(M_J)$ then the vertices on the subdivision on one of the edges of $𝒫$ incident on $v$ cannot be visited anymore. By setting $\mathrm{\ell }$ large enough, we show that it is detrimental for the algorithm to use such vertices to connect to $V(M_J)$, which renders the edges of $M_J$ indispensable for a long path. As above, the actual lower bound construction is more involved since we need to turn Alice’s RS-graph into an input distribution. On a technical level, we give a reduction to the two-party communication problem Index using ideas similar to those introduced by Dark and Konrad [15].

Undirected Graphs in the Insertion-deletion Model. The key advantage that allows us to prove a much stronger lower bound for insertion-deletion streams than for insertion-only streams is that Bob can insert edge deletions that turn a large matching contained in Alice’s edges $E_A$ into an induced matching. We see that it is possible to achieve this so that:

1. 1.

   The special (induced) matching $M$ is of size $n-O(n/\alpha )$; and

2. 2.

   The special matching $M$ is hidden among Alice’s edges.

Furthermore, we make sure that there exists a second matching $N$ such that $N\cup M$ forms a path of length $\mathrm{\Omega }(n)$. Property 1 significantly helps in proving our lower bound since, as opposed to our lower bound for undirected graphs in insertion-only streams, there are only $O(n/\alpha )$ vertices outside the set $V(M)$, and, hence, these vertices only allow us to visit $O(n/\alpha )$ vertices of $V(M)$. We can then argue that, for the remaining $n-O(n/\alpha )$ vertices of $V(M)$, Bob is required to know the edges of $M$ for those to be visited. This however requires Alice to send these edges to Bob. Then, Property 2 ensures that Alice cannot identify these edges and would therefore have to send most edges of the input graph to Bob, which exceeds the allowed communication budget. On a technical level, we give a reduction to the Augmented-Index two-party communication problem, again, reusing many of the ideas given in the lower bound by Dark and Konrad [15].

Given the input graph $G=(V,E)$, let $U\subseteq V$ denote a subset of vertices of $V$ such that $G[U]$ has minimum degree at least $d/2$. It is well-known that such a subset of vertices exists (see Lemma 19 for completeness).

Let $u_0\in U$ be any vertex, and let $P_0=\{u_0\}$ be the path of length $0$ with start and end point $u_0$. We will extend $P_0$ using the edges in $F$ that are also contained in $G[U]$, as follows:

In step $i=1,2,\mathrm{\dots },d/3$, we add the edge $(u_{i-1},u_i)$ to $P_{i-1}$ and obtain the path $P_i$. The edge $(u_{i-1},u_i)$ is an arbitrary edge in $F$ incident on $u_{i-1}$ that connects to a vertex $u_i\in U$ that has not yet been visited on the path $P_{i-1}$. We will now prove that such a vertex exists.

First, recall that, by definition of $U$, the vertex $u_{i-1}$ has at least $d/2$ neighbors in $G[U]$. Since $i\le d/3$, at least $d/2-d/3=d/6$ of these neighbors are not visited by the path $P_{i-1}$. Denote by $E(u_{i-1})$ this set of at least $d/6$ edges connecting $u_{i-1}$ to not yet visited neighbors in $G[U]$. We now claim that at least one of the edges of $E(u_{i-1})$ is contained in $F$ with high probability. Observe that at stage $i-1$, we have only learnt so far that the sample $F$ contains the $i-1$ edges of the path $P_{i-1}$. Hence,

where we used the inequality $\frac{\left(\genfrac{}{}{0pt}{}{a-c}{b}\right)}{\left(\genfrac{}{}{0pt}{}{a}{b}\right)}\le \exp \left(-\frac{bc}{a}\right)$ (see Lemma 18) to obtain the first inequality and the bound $(i-1)\le n\ln (n)$ to obtain the second.

We can therefore extend the path with probability $1-\frac{1}{n^3}$ at any step $i$. Since we run $d/3\le n$ steps overall to create the final path $P_{d/3}$ of length $d/3$, by the union bound, we succeed with probability at least $1-\frac{1}{n^2}$. Last, since a longest path in $G$ is of length at most $n$, the algorithm also constitutes an $O(n/d)$-approximation algorithm to Longest Path. $◀$

For an input graph $H=(A,B_1\cup B_2,E)\sim {𝒟}_{\text{SLP}}(r)$ with $B_1=\{b_1^1,\mathrm{\dots },b_r^1\}$ and $B_2=\{b_1^2,\mathrm{\dots },b_r^2\}$, let $H^{\prime }$ be the graph obtained from $H$ by contracting the vertex pairs $b_i^1$ and $b_i^2$, for all $i$, and by treating parallel edges in the resulting graph as single edges, see Figure 3 for an illustration. It is easy to see that $\mathrm{lp}(H^{\prime })=\mathrm{lp}(H)$. Furthermore, denote by ${𝒟}_{\text{SLP}}^{\prime }(r)$ the distribution of $H^{\prime }$. Observe that ${𝒟}_{\text{SLP}}(r)$ and ${𝒟}_{\text{SLP}}^{\prime }(r)$ are uniform distributions over their respective supports.

Next, consider the set ${\mathrm{\Sigma }}_r$ of permutations of the set $\{1,2,\mathrm{\dots },r\}$. Consider now the bijection $f:{\mathrm{\Sigma }}_r\to \text{range}({𝒟}_{\text{SLP}}^{\prime }(r))$, where a permutation $\sigma \in {\mathrm{\Sigma }}_r$ is mapped to the graph that contains the edges $(b_i,a_{\sigma (i)})$, for all $i$. Then, we observe that, for a permutation $\sigma \in {\mathrm{\Sigma }}_r$, the length of the longest cycle $\mathrm{lc}(\sigma )$ is related to $\mathrm{lp}(f(\sigma ))$ as follows:

It is known that the expected length of a longest cycle in a random permutation $\sigma \in {\mathrm{\Sigma }}_r$ is at least $\lambda \cdot r$, where $\lambda =0.624\mathrm{\dots }$ is the Golomb-Dickman constant [20, 19]. Hence, we obtain

using the assumption that $r$ is large enough. Since the longest paths in $H$ and $H^{\prime }$ are identical, the result follows. $◀$

Next, we show that any deterministic protocol on distribution ${𝒟}_{\text{SLP}}(r)$ that communicates at most $\frac{1}{100}r$ bits outputs a path of length $O(\log r)$ with high probability over ${𝒟}_{\text{SLP}}(r)$.

Denote by $ℳ$ the set of possible directed input matchings $M$ for Alice in ${𝒟}_{\text{SLP}}(r)$. Then, $|ℳ|=2^r$. Next, since every message sent by protocol ${\mathrm{\Pi }}_{\text{SLP}}$ is of length at most $s:=r/100$, there are at most $2^s$ different messages. On average, a message therefore corresponds to $2^{r-s}$ inputs, and, at most $\frac{1}{1000}\cdot 2^r$ inputs yield messages that in turn only correspond to at most $\frac{1}{1000}{2}^{r-s}$ inputs. Hence, at least $\frac{999}{1000}{2}^r$ inputs yield messages that each correspond to at least $\frac{1}{1000}{2}^{r-s}$ inputs. Consider now one of these messages $\pi$, and let $M_1,M_2,\mathrm{\dots }$ be the matchings $M$ that correspond to $\pi$. Given $\pi$, the protocol can only output an edge if it is contained in all matchings $M_i$. Suppose that there are $k$ such edges. Then, there are at most $2^{r-k}$ input graphs that contain these edges. We then have:

which implies $k\le s+10$.

Denote by $K$ this set of at most $k\le s+10$ edges. We will now prove that the longest path in $K\cup E_B$ is of length $O(\log r)$ with high probability.

Denote by $A^{\prime }$ the $A$-endpoints of the edges $K$, and let $a_0^{\prime }\in A^{\prime }$ be any vertex. We bound the length of the path with starting point $a_0^{\prime }$. This path first uses the edge in $K$ incident on $a_0^{\prime }$, and denote by $b_0^{\prime }$ the other endpoint of this edge. Then, the path uses the edge of $N_1$ or $N_2$ incident on $b_0^{\prime }$ to return to an $A$-vertex that we denote by $a_1^{\prime }$. Observe that we can only continue on this path if $a_1^{\prime }\in A^{\prime }$. If this is the case then we can continue in the same fashion, visit a $B$-vertex $b_1^{\prime }$, and return to another $A$-vertex $a_2^{\prime }$. Again, we can only continue if $a_2^{\prime }\in A^{\prime }$, and so on. For any $i\ge 1$, the following holds:

assuming that $r$ is large enough. Hence, the probability that the path contains $p+2$ $A^{\prime }$-vertices and is thus of length $2(p+1)$ is at most $\frac{1}{{50}^p}$. This further implies that, with probability at least $1-\frac{1}{r^2}$, the path is of length $O(\log r)$.

Observe that the argument above applies when considering any start vertex in $A^{\prime }$. Hence, by a union bound over all possible start vertices in $A^{\prime }$, all paths starting at an $A^{\prime }$ vertex are of length $O(\log r)$ with probability at least $1-\frac{1}{r}$. Last, observe that a longest path that may be able to form could also start at a $B$-vertex. Such a path however is only by one edge longer than a path starting at an $A$-vertex. The $O(\log r)$ length bound therefore still holds.

So far, we proved that for a message that corresponds to at least $\frac{1}{1000}{2}^{r-s}$ inputs, Bob can only output a path of length at most $O(\log r)$ with high probability, where the probability is over Bob’s input. Hence, overall, for a uniform input from ${𝒟}_{\text{SLP}}(r)$, the probability that Bob will output a path of length $O(\log r)$ is at least $\frac{999}{1000}\cdot (1-\frac{1}{r})\ge \frac{998}{1000}$ for $r$ large enough. $◀$ We use the notation ${\text{LP}}_{ϵ}^{\alpha }$ to denote LP with approximation factor $\alpha$ and error probability $ϵ$.

Towards a contradiction, let ${\mathrm{\Pi }}_{\text{r}}$ be a randomized protocol for Longest Path on inputs from ${𝒟}_{\text{SLP}}(r)$ with approximation factor $o(r/\log r)$ that errs with probability at most $1/4$. Given ${\mathrm{\Pi }}_{\text{r}}$, by Yao’s Lemma, there exists a deterministic protocol ${\mathrm{\Pi }}_{\text{d}}$ on distribution ${𝒟}_{\text{SLP}}(r)$ with distributional error $1/4$ and approximation factor $o(r/\log r)$, i.e., on at least $3/4$ of the inputs, the protocol achieves a $o(r/\log r)$-approximation.

Lemma 11 states that ${𝔼}_{H\leftarrow {𝒟}_{\text{SLP}}(r)}\mathrm{lp}(H)\ge 1.24r$. This allows us to bound the quantity ${\mathrm{Pr}}_{H\leftarrow {𝒟}_{\text{SLP}}(r)}[\mathrm{lp}(H)\ge \frac{1}{2}r]$, as follows:
$1.24r\le \underset{H\leftarrow {𝒟}_{\text{SLP}}(r)}{𝔼}\mathrm{lp}(H)$ $\le \underset{H\leftarrow {𝒟}_{\text{SLP}}(r)}{\mathrm{Pr}}[\mathrm{lp}(H)\ge {\displaystyle \frac{1}{2}}r]\cdot 2r+(1-\underset{H\leftarrow {𝒟}_{\text{SLP}}(r)}{\mathrm{Pr}}[\mathrm{lp}(H)\ge {\displaystyle \frac{1}{2}}r]){\displaystyle \frac{1}{2}}r$ $=r\cdot \left(1.5\cdot \underset{H\leftarrow {𝒟}_{\text{SLP}}(r)}{\mathrm{Pr}}[\mathrm{lp}(H)\ge {\displaystyle \frac{1}{2}}r]+{\displaystyle \frac{1}{2}}\right),$

where we used the fact that the longest path in $H$ is at most the number of vertices in $H$, i.e., $2r$. The previous inequality then implies that ${\mathrm{Pr}}_{H\leftarrow {𝒟}_{\text{SLP}}(r)}[\mathrm{lp}(H)\ge \frac{1}{2}r]\ge \frac{1.24-0.5}{1.5}\ge \frac{1}{3}$.

Next, Lemma 12 states that, with probability at least $1-\frac{1}{500}$, ${\mathrm{\Pi }}_{\text{d}}$ outputs a path of length at most $O(\log r)$. Hence, with probability at least $1/3-1/500>1/4$, there simultaneously exists a longest path of length at least $\frac{1}{2}r$ and ${\mathrm{\Pi }}_{\text{d}}$ outputs one of length $(O\log r)$. The approximation factor of ${\mathrm{\Pi }}_{\text{d}}$ is therefore $\mathrm{\Omega }(r/\log r)$, contradicting the fact that ${\mathrm{\Pi }}_d$ achieves an approximation factor of $o(r/\log r)$ on at least $3/4$ of the instances. Protocols ${\mathrm{\Pi }}_d$ and ${\mathrm{\Pi }}_r$ therefore do not exist, which completes the proof. $◀$

Denote by $\mathrm{\Pi }$ a randomized one-way two-party communication protocol for ${\text{LP}}_{1/4-\frac{1}{100}}^{O(r/\log r)}$ on inputs from ${𝒟}_{\text{SLP}}(r)$. Given $\mathrm{\Pi }$, using the message compression technique stated in Theorem 9, we obtain a protocol ${\mathrm{\Pi }}^{\prime }$ for ${\text{LP}}_{1/4-\frac{1}{100}}^{O(r/\log r)}$ that sends a message of expected size (recall that $M$ is Alice’s input matching)

where the expectation is taken over the randomness used by the protocol. Then, by the Markov inequality, the probability that the message is of size at least $100\cdot s$ is at most $\frac{1}{100}$.

Given ${\mathrm{\Pi }}^{\prime }$, we now construct a protocol ${\mathrm{\Pi }}^{\prime \prime }$ with maximum message size $100\cdot s$ that solves LP with slightly increased error: Whenever ${\mathrm{\Pi }}^{\prime }$ sends a message of size at most $100\cdot s$, ${\mathrm{\Pi }}^{\prime \prime }$ also sends this message and the protocol behaves exactly the same as ${\mathrm{\Pi }}^{\prime }$. However, when ${\mathrm{\Pi }}^{\prime }$ sends a message of size at least $100\cdot s$, ${\mathrm{\Pi }}^{\prime \prime }$ aborts and thus fails. Since the probability of sending a message of size larger than $100\cdot s$ is $1/100$, the error probability of ${\mathrm{\Pi }}^{\prime \prime }$ is $(\frac{1}{4}-\frac{1}{100})+\frac{1}{100}=\frac{1}{4}$. From Theorem 13, we obtain that the communication cost of ${\mathrm{\Pi }}^{\prime \prime }$ is $\mathrm{\Omega }(r)$, which implies that $100\cdot s=\mathrm{\Omega }(r)$. Hence, combined with Inequality 1, we conclude that

where the inequality follows from property P1 stated in the preliminaries. $◀$

Let $𝒫$ be a path of length at least $2$ in $G$. Since $G$ is bipartite, every other edge in $𝒫$ must be an edge from $N_J^1\cup N_J^2$ since these are the only edges with head in $A$. Observe that the edges $M_J$ are the only edges with both endpoints in $A(N_J^1\cup N_J^2)$ and $B(N_J^1\cup N_J^2)$. Hence, for any three consecutive edges $e,f,g$ in path $𝒫$, if $e$ and $g$ are edges from $N_J^1\cup N_J^2$, then $f$ must be an edge from $M_J$. It follows that if an edge that is not contained in $M_J\cup N_J^1\cup N_J^2$ is included in $𝒫$ then this edge must be the first or the last edge of $𝒫$. $◀$

Given our reduction, we now relate the information costs of ${\mathrm{\Pi }}_{\text{SLP}}(r)$ and ${\mathrm{\Pi }}_{\text{LP}}(n)$:

We denote by $R_{\text{SLP}}$ and $R_{\text{LP}}$ the public randomness used in ${\mathrm{\Pi }}_{\text{SLP}}(r)$ and in ${\mathrm{\Pi }}_{\text{LP}}(n)$, respectively. Then (see the rules P1, …, P4 in the preliminaries):

Regarding the approximation factor, observe that $\mathrm{lp}(H)\le \mathrm{lp}(G)$. Furthermore, by Lemma 15, the path found by ${\mathrm{\Pi }}_{\text{SLP}}(r)$ is at most by $2$ shorter than the path found by ${\mathrm{\Pi }}_{\text{LP}}(n)$, which in turn is of length at least $\mathrm{lp}(G)/\alpha$. Hence, the approximation factor of ${\mathrm{\Pi }}_{\text{SLP}}(r)$ is bounded by $\frac{\mathrm{lp}(H)}{\mathrm{lp}(G)/\alpha -2}\le \frac{\mathrm{lp}(G)}{\mathrm{lp}(G)/\alpha -2}=O(\alpha )$. $◀$ We are now ready to state our main lower bound result for directed graphs.

Let ${\mathrm{\Pi }}_{\text{LP}}(n)$ be a protocol for ${\text{LP}}_{1/4-\frac{1}{500}}^{O(r/\log r)}(n)$. Then, from Lemmas 16 and 14, we obtain

Since the choice of ${\mathrm{\Pi }}_{\text{LP}}(n)$ was arbitrary, and information complexity is a lower bound on communication complexity, the result follows. $◀$

Finally using the well-known connection between streaming algorithms and one-way two-party communication protocols as well as the RS-graph construction by Alon et al. as stated in Theorem 7, we obtain the following theorem: