7
$\begingroup$

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

Improve this question
$\endgroup$
11
  • 2
    $\begingroup$ I was actually wondering about this exact issue on your weekly quiz! $\endgroup$
    – Huck Bennett
    Mar 22, 2021 at 0:54
  • 3
    $\begingroup$ I reckon that is a mistake/inaccuracy. Surely you would need enough time to read the entire input. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Mar 22, 2021 at 8:18
  • 2
    $\begingroup$ 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... en.m.wikipedia.org/wiki/… ... maybe it was implicit that the degrees are bounded? $\endgroup$
    – Ryan Williams
    Mar 22, 2021 at 14:28
  • 1
    $\begingroup$ @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. $\endgroup$
    – Yonatan N
    Mar 22, 2021 at 18:17
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Yonatan N
    Mar 22, 2021 at 22:59

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.