2
$\begingroup$

There are 3 types of connectivity when talking about a directed graph $G$.

1) weakly connected - replacing all of $G$'s directed edges with undirected edges produces a connected (undirected) graph.

2) connected - contains a directed path from $u$ to $v$ OR a directed path from $v$ to $u$ for every pair of vertices $u$, $v$

3) strongly connected - contains a directed path from $u$ to $v$ AND a directed path from $v$ to $u$ for every pair of vertices $u$, $v$


Efficient algorithm for determining...

weak connectivity - replace $G$'s directed edges with undirected edges and run DFS and see if it reaches every vertex

connectivity - ???

strong connectivity - run DFS on $G$ and see if it reaches every vertex, and then transpose $G$ (reverse each edge in $G$ to yield a new graph $G^T$) and run DFS on $G^T$ and see if it reaches every vertex (since the existence of a path from $u$ to $v$ in $G^T$ implies the existence of a path from $v$ to $u$ in $G$)

What is an efficient algorithm for determining if a directed graph G is connected in this intermediate sense between weak and strong?

EDIT:

I realized "efficient" is pretty vague. So more specifically, I mean that the algorithms I provided for weak connectivity and strong connectivity run in linear time ($O(V + E)$), and the naive algorithm for the intermediate connectivity of running all-pairs path finding and for each pair of vertices $(u, v)$ seeing if a path exists between them in either direction would run in something like $O(V^3)$ or $O(EV\ln{V})$. So I'm wondering if there is a linear time algorithm (or at least something better than the naive approach) to determining this intermediate connectivity, and what that might be.

$\endgroup$
  • 2
    $\begingroup$ This intermediate "connectivity" for directed graphs does not seem to be a standard concept. I can find no reference to it outside the Wikipedia page for Connectivity (graph theory). Probably this is because, unlike either weak or strong connectivity, it fails to be transitive, thus not meeting the basic requirements for what "connected" ought to mean. $\endgroup$ – Nick Matteo Jan 17 '16 at 1:02
  • $\begingroup$ Hmm, ok. Yeah, I got the concept from Wikipedia. To be honest, I don't particularly care about it if it's not a standard concept. Can you elaborate on what you mean by "transitive"? $\endgroup$ – tscizzle Jan 17 '16 at 1:14
  • $\begingroup$ With that definition, when a vertex $u$ is connected to a vertex $v$, and $v$ is connected to $w$, then $u$ is not necessarily connected to $w$. $\endgroup$ – Nick Matteo Jan 17 '16 at 1:23
  • $\begingroup$ Ah, ok. I see now. $\endgroup$ – tscizzle Jan 17 '16 at 2:27
  • 1
    $\begingroup$ @Ben but isn't that not enough, because $u$ having a path to or from every $v0$ and $v1$ doesn't imply that $v0$ has a path to or from $v1$? $\endgroup$ – tscizzle Jan 17 '16 at 3:58
0
$\begingroup$

Two quick comments:

a) for strong connectedness you could save a little bit of time running DFS from one "hub" vertex $h$ in $G$ and then DFS for the same $h$ in $G^T$. Obviously if you have path $u\rightarrow h$ and $h\rightarrow v$ for any vertices $u$, $v$ then you have path from $u$ to $v$.

b) for your semi-connectivity (from item 2) there is an expensive way to do that by building the entire connectedness matrix $M = C(G)$ for $G$ -- and then we check that all elements in $M+M^T$ are positive. On the bright(er) side, DFS-like algorithm for $C(G)$-computation will allow you to build entire strong connectedness components which makes computing $C(G)$ a little easier.

$\endgroup$
0
$\begingroup$

This type of intermediate connectivity is often called semi-connectivity. If you used this notion you would find out that your question already has a very comprehensive answer on stackoverflow: https://stackoverflow.com/questions/30642383/determine-if-a-graph-is-semi-connected-or-not

I will sketch it here simplified though.

Idea is to reduce problem by reducing digraph G to it's graph of SCC's, say G', that is always acyclic and then try to find a path that covers all nodes in G'. If there is no such path then it's not possible to get from some SCC to some other (G' is acyclic) and that means that vertices in them have no connections. Otherwise G' is semi-connected and so is G.

Input: digraph G = (V,E)

Output: true or false if it's semi-connected

init graph G'=(V',E') from SCC's of G where V' is set of SCC of G and E' are edges between them or $E'=\{(v_1',v_2') | v_1',v_2'\in V'$ and $\exists (v_1,v_2)\in E$, $v_1 \in v_1',v_2 \in v_2'$} // G' guaranteed to be acyclic and this can be done in O(|V| + |E|), for example, using Kosaraju's algorithm

find topological ordering $T=(v_0,...,v_{|V'|})$ of G' // correct as G' is acyclic and also can be done in O(|V'| + |E'|) using modification of DFS.

if some possible pair $(v_i,v_{i+1})$ in T is not in E' ouput false, otherwise true // if not then $(v_{i+1},v_{i})$ also is not in E' and there is no connection between vertices in $v_i$ and $v_{i+1}$, takes O(|V'|)

$\endgroup$
0
$\begingroup$

To check for "regular connected" (semi-connected) directed graph $G$:

1) Form the condensation of $G$ (linear time), giving a directed acyclic graph $H$

2) If $H$ is a (directed) path, $G$ is "regular connected". (If $H$ has multiple branches, sources or sinks, $G$ is not "regular connected").

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