Cfrgtkky

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(EVln{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.

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 $urightarrow h$ and $hrightarrow 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.

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'|)

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