# Can we test whether two vertices are connected in time linear in the number of nodes?

Consider the problem:

Given an undirected graph and two of its vertices, is there a path between them?

I often read that this problem can be solved in linear time in the number of vertices! I am not sure why this claim holds.

Can this really be done in linear time (not amortized) without preprocessing?

-
Basic questions are totally welcome! However, you should always show your own effort. Why do you think it couldn't hold? What do you consider a problem? – Juho Apr 1 '14 at 15:38
@Juho Well it might hold, but I was suspicious because some linear time arguments involved BFS which has running time quadratic in $n$ – Luke Apr 1 '14 at 15:54
Are you sure you don't want a running time of $O(n+m)$, i.e. linear in the size of the input? – Pål GD Apr 1 '14 at 15:59
@Pål GD Maybe referring to it as a basic question was misleading. I was really looking for something which has running time linear in n, independent of m. – Luke Apr 1 '14 at 16:06
How are you to safely say no if you haven't considered all the edges? – Pål GD Apr 1 '14 at 16:48

It is not possible to decide $s$-$t$ connectivity in $O(n)$, in the adjacency matrix model. In fact, here is an $\Omega(n^2)$ lower bound. Let $|S| = |T| = n/2$ be a partition of the vertex set, and choose some $s \in S$ and $t \in T$. Consider the graph in which $S$ and $T$ are both cliques. In this graph $t$ is not reachable from $s$. If we add any edge from $S$ to $T$, then $t$ is reachable from $s$. A simple adversary argument shows that any algorithm that decides where $t$ is reachable from $s$ has to potentially check all $|S| \cdot |T| = n^2/4$ potential edges: if it didn't query some edge $(x,y)$, then it wouldn't be able to distinguish the case in which there is no edge from $S$ to $T$ (and so $t$ is not reachable from $s$) from the case in which $(x,y)$ is the unique edge from $S$ to $T$ (and so $t$ is reachable from $s$).

-

Your sources are sloppy or you misinterpret something. In general, deciding reachability requires time $\Omega(n+m)$ (assuming adjacency lists). This is linear in the input size (which is in $\Theta(m)$), however, so saying that reachability is solvable in linear time [in input size, which is the default] is correct.

For a proof of this lower bound, see Yuval's answer; the argument remains the same but we conclude that the algorithm must traverse all adjency lists of all nodes in $S$, which contain in total $\Omega(n^2)$ many entries.

-
How is the input size $\Theta(m)$? $\;\;\;$ The "obvious way" would need $\: m\cdot \Theta(\hspace{.02 in}\log(n)) \:$ bits. $\hspace{1.41 in}$ – Ricky Demer Apr 1 '14 at 18:19
@RickyDemer: I was assuming a uniform cost model for both time and space. If we switch to a logarithmic cost model, we get the space you state and/but also additional logarithmic factors in the runtime. – Raphael Apr 1 '14 at 18:39

Perhaps your source text is dealing with undirected graphs that fulfill some additional structural requirements. For example, for a tree, $m = n - 1$. Therefore, an algorithm that takes $O(n+m)$ time on a general graph actually runs in $O(n)$ time on trees since $n > m$.

-