# 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? 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? 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}$
– user12859
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$.