2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Juho Apr 1 '14 at 15:38
  • $\begingroup$ @Juho Well it might hold, but I was suspicious because some linear time arguments involved BFS which has running time quadratic in $n$ $\endgroup$ – Luke Apr 1 '14 at 15:54
  • $\begingroup$ Are you sure you don't want a running time of $O(n+m)$, i.e. linear in the size of the input? $\endgroup$ – Pål GD Apr 1 '14 at 15:59
  • $\begingroup$ @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. $\endgroup$ – Luke Apr 1 '14 at 16:06
  • $\begingroup$ How are you to safely say no if you haven't considered all the edges? $\endgroup$ – Pål GD Apr 1 '14 at 16:48
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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}$ $\endgroup$ – user12859 Apr 1 '14 at 18:19
  • $\begingroup$ @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. $\endgroup$ – Raphael Apr 1 '14 at 18:39
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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