3
$\begingroup$

I am trying to create an algorithm in linear time where if given a directed acyclic graph I can add edges to make it strongly connected components.

I believe I have an algorithm to identify sources and sinks in the input list of edges in form

1 2
2 5
3 1 
etc

And I know that the minimum number of edges to be added in order to create connected components is equal to MAX(sources,sinks).

My question is, is there a way to come up with where I should add edges so that I can have the minimum number and still be linear complexity?

Here is an example of what I'm after.

Given this input edges:

1 3
1 4
2 3
2 4
5 7
5 8
6 8
6 9

Output these edges to be added:

3 1
4 5
7 6
8 1
9 2
$\endgroup$

migrated from stackoverflow.com Oct 3 '12 at 11:37

This question came from our site for professional and enthusiast programmers.

  • $\begingroup$ Now that I think about it, constructing the set mentioned in stackoverflow.com/questions/8152749/… would take a lot of time, so it is not really linear. But it is a valid algorithm nonetheless. $\endgroup$ – ffao Oct 3 '12 at 1:42
3
$\begingroup$

Assuming there are no isolated vertices in the graph you only need to add $max(|\mbox{sources}|,|\mbox{sinks}|)$ edges to make it strongly connected.

Let $T = \lbrace t_1,\ldots,t_n\rbrace$ be the sinks and $\lbrace s_1,\ldots,s_m \rbrace$ be the sources of the DAG. Assume that $n \le m$ (the other case is similar). Consider a bipartite graph $G(T,S)$ between the two sets defined as follows: $G(T,S)$ has an edge $(t_i, s_j)$ if and only if $t_i$ can be reached from $s_j$.

Let $M$ be a maximal matching in $G(T,S)$. Without loss of generality assume that $M$ consists of $k$ edges: $\lbrace (t_1, s_1), (t_2, s_2), \ldots, (t_k, s_k) \rbrace$. In the original DAG $G$, add directed-edges $\lbrace (t_1\rightarrow s_2), (t_2\rightarrow s_3), \ldots, (t_{k-1}\rightarrow s_k),(t_k\rightarrow s_1)\rbrace$. It's easy to see that by adding these edges, the vertices induced by $M$ are strongly connected in $G$.

Now consider the remaining vertices in $G(T,S)$. Because $M$ is maximal, each vertex in $S-M$ (resp. $T-M$) should be connected to a vertex in $T$ (resp. $S-M$). So we pair up the remaining vertices arbitrarily, say $\lbrace (t_{k+1}, s_{k+1}), \ldots, (t_n, s_n)\rbrace$ and add the corresponding directed edges in $G$. For each remaining source vertex source $s_i$ ($i$ belongs to $\lbrace n+1,\ldots, m\rbrace$ we add the edge $(t_1\rightarrow s_i)$ in $G$. Thus the total number of edges added is $max(|\mbox{sources}|,|\mbox{sinks}|)$.

$\endgroup$

Your Answer

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