Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 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 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 at 16:06
    
How are you to safely say no if you haven't considered all the edges? –  Pål GD Apr 1 at 16:48
show 5 more comments

3 Answers 3

up vote 7 down vote accepted

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$).

share|improve this answer
add comment

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.

share|improve this answer
    
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 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 at 18:39
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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