<p>Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking <span class="math-container">$s$</span> and <span class="math-container">$t$</span> to correspond to the first and last indices respectively, we can prove that <span class="math-container">$\Omega(n^2)$</span> bits of the matrix may need to be read to decide STCONN even under the promise that the <span class="math-container">$(n/2)\times(n/2)$</span> square blocks in the top-left and bottom-right are all ones (with the necessary adjustments for odd <span class="math-container">$n$</span>).</p>
<p>Indeed, we have some <span class="math-container">$\Omega(n^2)$</span> entries unaccounted for in the matrix, and there is an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path iff any one of them is a <span class="math-container">$1$</span>. So in the worst case, we might need to read all of these <span class="math-container">$\Omega(n^2)$</span> bits to prove <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-non-connectivity (or half of them if the graph is known to be undirected, which doesn't change the order of growth). We can turn this into a lower bound against randomized algorithms by considering the case that with 50% probability we either add or don't add in a <span class="math-container">$1$</span> uniformly at random: we must read some <span class="math-container">$\Omega(\varepsilon n^2)$</span> bits to gain a <span class="math-container">$\varepsilon$</span> advantage over a random coin flip.</p>
<p>Graphically, this corresponds to the case where <span class="math-container">$s$</span> and <span class="math-container">$t$</span> each lie within disjoint cliques of size <span class="math-container">$n/2$</span>, and we wish to determine if there is at least one edge joining these cliques. One can also do the same thing with any other pair of connected structures of order <span class="math-container">$\Omega(n)$</span> each.</p>

CC BY-SA 4.0
2021-03-23T04:34:56.877Z
2021-03-23T04:34:56.877Z
Yonatan N
<p>This is a very basic question on <span class="math-container">$s$</span>-<span class="math-container">$t$</span>-connectivity in directed graphs. As a baseline, using DFS (or BFS), one can solve the problem on a graph <span class="math-container">$G=(V,E)$</span> in <span class="math-container">$O(n+m)$</span> time and <span class="math-container">$O(n)$</span> space, where <span class="math-container">$n=|V|$</span> and <span class="math-container">$m=|E|$</span>.</p>
<p>However, I have seen mentioned in several places that DFS/BFS let you solve the problem in <span class="math-container">$O(n)$</span> time and space. For instance:</p>
<blockquote>
<p>Two basic results on the complexity of <span class="math-container">$\mathsf{STCONN}$</span> exist for over 20 years. The first follows from the discovery of the very efficient algorithms for graph traversal, BFS (Breadth-First Search) and DFS (Depth-First Search), which use only linear time and space in <span class="math-container">$n$</span>, the number of vertices.</p>
<p><strong>Theorem 4.</strong> <span class="math-container">$\mathsf{STCONN}\in\mathrm{TISP}(n,n)$</span>.</p>
</blockquote>
<p>from [1]. How does that work? (Sorry if this question is trivial...) I would have thought maybe this followed from taking <span class="math-container">$n$</span> as the input size (not the number of vertices), but the text before does contradict this interpretation.</p>
<hr />
<p>[1] Avi Wigderson.
<em>The Complexity of Graph Connectivity</em>. MFCS 1992: 112-132</p>

CC BY-SA 4.0
2021-03-22T00:54:58.720Z
I was actually wondering about this exact issue on your weekly quiz!
Huck Bennett
CC BY-SA 4.0
2021-03-22T08:18:01.750Z
I reckon that is a mistake/inaccuracy. Surely you would need enough time to read the entire input.
Kristoffer Arnsfelt Hansen
CC BY-SA 4.0
2021-03-22T14:28:05.637Z
To formalize what Kristoffer said a bit,  connectivity is a nontrivial monotone graph property and thus needs query complexity at least Omega(n^2) in dense n-node graphs. I can't see how one could get around this... https://en.m.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture  ... maybe it was implicit that the degrees are bounded?
Ryan Williams
CC BY-SA 4.0
2021-03-22T18:17:05.827Z
@RyanWilliams $s$-$t$ graph connectivity requires an explicit labeling of $s$ and $t$, so strictly speaking it is not a graph property and the standard set of graph evasiveness results need not (directly) apply. As a trivial example, consider the still-monotone modification where we also require the $s$-$t$ path length to equal $1$. That said, the usual adversarial approach, in which the edge existence oracle keeps answering "no" to all queries until doing so would induce an $s$-$t$ cut, can  still be used to derive an $\Omega(n^2)$ lower bound in the edge query model.
Yonatan N
CC BY-SA 4.0
2021-03-22T20:10:46.297Z
@YonatanN I don’t think this argument holds for a graph given as an adjacency list? I think that would correspond to a different query model, eg “give me the i-the neighbour of vertex u”
Sasho Nikolov
CC BY-SA 4.0
2021-03-22T22:06:39.623Z
@SashoNikolov Agreed. The model I was referring to is one where you can query the entries of the adjacency matrix one at a time for some unit cost until you have sufficient information to give a provably correct answer. This is probably the context most closely connected to the evasiveness corpus of work. The above adversary would only ever give responses which construct a forest, which makes for an exceptionally poor lower bound for most other cost models such as your adjacency list example =).
Yonatan N
CC BY-SA 4.0
2021-03-22T22:29:28.433Z
@KristofferArnsfeltHansen Surely, yes... but there are quite a few suprising results in TCS I wouldn't have guessed were possible. (I also checked the paper, there seems to be no implicit assumption that the graph is bounded; specifically, bounded-degree graphs are explicitly mentioned as a specific different direction, later; also, the graphs are presented as adjacency matrices): *"We will assume that graphs are represented by their adjacency matrix (as this representation captures the monotonicity of connectivity), though most results hold in any other standard representation."*
Clement C.
CC BY-SA 4.0
2021-03-22T22:59:19.987Z
When given as a standard-form adjacency matrix with $s$ at the first index and $t$ in the last, the problem requires us to read $\Omega(n^2)$ entry queries even under the additional promise that the top left and bottom right $(n/2)$-by-$(n/2)$ blocks are all $1$: to prove that $s$ and $t$ are disconnected, one would need to ascertain that the other $\Omega(n^2)$ entries of the matrix are all $0$.
Yonatan N
CC BY-SA 4.0
2021-03-23T03:54:24.013Z
@YonatanN If you could make that into an answer, I'd be happy to accept it.
Clement C.
CC BY-SA 4.0
2021-03-23T22:09:20.647Z
@YonatanN right, I didn't cite precisely the correct thing, but a query complexity lower bound still (obviously?) holds, by a reduction from OR.
Ryan Williams
CC BY-SA 4.0
2021-03-23T22:09:24.807Z
@ClementC you are right to ask to confirm, as there are some problems which only need O(n) time, surprisingly. One example that comes to mind is that you can find a +1 approximation to the shortest cycle in only O(n) time, by (roughly speaking) running BFS and cutting it off when it repeats a node. See https://theory.stanford.edu/~virgi/cs267/lecture2.pdf. This needs an adjacency list representation at the very least, though.
Ryan Williams
<graph-algorithms>
STCONN in $O(n)$ time?
Clement C.
# STCONN in $O(n)$ time?

(Asked by: username_0 on 2021-03-21)

This is a very basic question on $s$-$t$-connectivity in directed graphs. As a baseline, using DFS (or BFS), one can solve the problem on a graph $G=(V,E)$ in $O(n+m)$ time and $O(n)$ space, where $n=|V|$ and $m=|E|$.

However, I have seen mentioned in several places that DFS/BFS let you solve the problem in $O(n)$ time and space. For instance:

> Two basic results on the complexity of $\mathsf{STCONN}$ exist for over 20 years. The first follows from the discovery of the very efficient algorithms for graph traversal, BFS (Breadth-First Search) and DFS (Depth-First Search), which use only linear time and space in $n$, the number of vertices.
>
> **Theorem 4.** $\mathsf{STCONN}\in\mathrm{TISP}(n,n)$.

from [1]. How does that work? (Sorry if this question is trivial...) I would have thought maybe this followed from taking $n$ as the input size (not the number of vertices), but the text before does contradict this interpretation.

---

[1] Avi Wigderson.
*The Complexity of Graph Connectivity*. MFCS 1992: 112-132

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: I was actually wondering about this exact issue on your weekly quiz!  
> **username_2**: I reckon that is a mistake/inaccuracy. Surely you would need enough time to read the entire input.  
> **username_3**: To formalize what Kristoffer said a bit,  connectivity is a nontrivial monotone graph property and thus needs query complexity at least Omega(n^2) in dense n-node graphs. I can't see how one could get around this... https://en.m.wikipedia.org/wiki/Aanderaa%E2%80%93Karp%E2%80%93Rosenberg_conjecture  ... maybe it was implicit that the degrees are bounded?  
> **username_4**: @RyanWilliams $s$-$t$ graph connectivity requires an explicit labeling of $s$ and $t$, so strictly speaking it is not a graph property and the standard set of graph evasiveness results need not (directly) apply. As a trivial example, consider the still-monotone modification where we also require the $s$-$t$ path length to equal $1$. That said, the usual adversarial approach, in which the edge existence oracle keeps answering "no" to all queries until doing so would induce an $s$-$t$ cut, can  still be used to derive an $\Omega(n^2)$ lower bound in the edge query model.  
> **username_5**: @YonatanN I don’t think this argument holds for a graph given as an adjacency list? I think that would correspond to a different query model, eg “give me the i-the neighbour of vertex u”  
> **username_4**: @SashoNikolov Agreed. The model I was referring to is one where you can query the entries of the adjacency matrix one at a time for some unit cost until you have sufficient information to give a provably correct answer. This is probably the context most closely connected to the evasiveness corpus of work. The above adversary would only ever give responses which construct a forest, which makes for an exceptionally poor lower bound for most other cost models such as your adjacency list example =).  
> **username_0**: @KristofferArnsfeltHansen Surely, yes... but there are quite a few suprising results in TCS I wouldn't have guessed were possible. (I also checked the paper, there seems to be no implicit assumption that the graph is bounded; specifically, bounded-degree graphs are explicitly mentioned as a specific different direction, later; also, the graphs are presented as adjacency matrices): *"We will assume that graphs are represented by their adjacency matrix (as this representation captures the monotonicity of connectivity), though most results hold in any other standard representation."*  
> **username_4**: When given as a standard-form adjacency matrix with $s$ at the first index and $t$ in the last, the problem requires us to read $\Omega(n^2)$ entry queries even under the additional promise that the top left and bottom right $(n/2)$-by-$(n/2)$ blocks are all $1$: to prove that $s$ and $t$ are disconnected, one would need to ascertain that the other $\Omega(n^2)$ entries of the matrix are all $0$.  
> **username_0**: @YonatanN If you could make that into an answer, I'd be happy to accept it.  
> **username_3**: @YonatanN right, I didn't cite precisely the correct thing, but a query complexity lower bound still (obviously?) holds, by a reduction from OR.  
> **username_3**: @ClementC you are right to ask to confirm, as there are some problems which only need O(n) time, surprisingly. One example that comes to mind is that you can find a +1 approximation to the shortest cycle in only O(n) time, by (roughly speaking) running BFS and cutting it off when it repeats a node. See https://theory.stanford.edu/~virgi/cs267/lecture2.pdf. This needs an adjacency list representation at the very least, though.  

---

## 1 answers

### Answer by username_4 on 2021-03-23. Score: 4 | Accepted answer

Per the section quoted in the comments, it appears that one of the cited documents takes input in the form of an adjacency matrix. In this scenario, taking $s$ and $t$ to correspond to the first and last indices respectively, we can prove that $\Omega(n^2)$ bits of the matrix may need to be read to decide STCONN even under the promise that the $(n/2)\times(n/2)$ square blocks in the top-left and bottom-right are all ones (with the necessary adjustments for odd $n$).

Indeed, we have some $\Omega(n^2)$ entries unaccounted for in the matrix, and there is an $s$-$t$ path iff any one of them is a $1$. So in the worst case, we might need to read all of these $\Omega(n^2)$ bits to prove $s$-$t$-non-connectivity (or half of them if the graph is known to be undirected, which doesn't change the order of growth). We can turn this into a lower bound against randomized algorithms by considering the case that with 50% probability we either add or don't add in a $1$ uniformly at random: we must read some $\Omega(\varepsilon n^2)$ bits to gain a $\varepsilon$ advantage over a random coin flip.

Graphically, this corresponds to the case where $s$ and $t$ each lie within disjoint cliques of size $n/2$, and we wish to determine if there is at least one edge joining these cliques. One can also do the same thing with any other pair of connected structures of order $\Omega(n)$ each.


---

