Jan 30. Strong connectivity in directed graphs.

Edge Connectivity

Recall that we defined a graph to be $2$-edge connected if for any edge $e \in E(G)$, $G\setminus \{e\}$ is still connected. Another way to define $2$-edge connectivity would be if for every pair of vertices $i,j \in V(G)$, there are atleast two edge disjoint paths from $i$ to $j$. It turns out these two definitions are the same. Notice that one direction is trivial: if every pair of vertices $i,j$ have atleast two edge disjoint paths between them, then removing an edge $e \in E(G)$ can destroy at most one of these paths, hence $G\setminus \{e\}$ is still connected. The other direction is left as an exercise.

Connectivity in directed graphs

Strongly connected graphs:  A directed graph $D = (V, A)$ is strongly connected if for every pair of vertices $u, v \in V(G)$ there is a directed path in $D$ from $u$ to $v$ and a directed path from $v$ to $u$.

Note that if we ignore arc directions, then a strongly connected graph is also $2$-edge connected. This may be seen for example by observing that strong connectivity implies that for every edge $e$, $G\setminus \{e\}$ is still connected.

Algorithm for finding the strongly connected components

Recall that we can use $DFS$ to discover the $2$-edge connected components of an undirected graph. An initial approach might be to convert $D$ to an undirected graph and use the algorithm for $2$-edge connectivity on $G$. However, while a strongly connected component is always a subset of a $2$-edge connected component, the converse unfortunately is not true.

Another approach is the following:

• Run $DFS$ on $D$ and every time $DFS$ finishes expanding a vertex $v$, add $v$ to a stack $S$.
• Let $D^R$ be the graph $D$ with the direction of all the arcs reversed.
• While the stack $S$ is non-empty, pop a vertex $v$ from $S$ and perform $DFS$ on $D^R$ starting at $v$. Let $U$ be the set of all the vertices visited by $DFS(v)$. Then $U$ is the strongly connected component containing $v$. Remove $U$ from $S$ and repeat.

This algorithm is known as Kosaraju’s algorithm and gives the strongly connected components of $D$.