6
$\begingroup$

A digraph is called weakly connected if its underlying undirected graph is connected.

You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of the out-neighbours of each vertex. You are also given $O(V)$ words of working memory, where a word is just large enough to hold an integer of magnitude $O(E)$.

Can you test $G$ for weak connectivity in $O(V+E)$ time?

Note that you are not given lists of the in-neighbours of each vertex and you don't have enough space to construct them.

Using the standard union-find algorithm, it can be done in $O(V+E\,\alpha(E))$ time for $\alpha$ being some Ackermann function inverse. Can you do better?

$\endgroup$
1
  • 1
    $\begingroup$ I would love an answer to this in either direction. If it's not getting attention here, maybe it should be migrated to cstheory? $\endgroup$ Jun 23, 2015 at 15:41

0

Your Answer

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