Minimal addition to strongly connected graph

Question

I have a set of nodes and set of directed edges between them. The edges have no weight.

How can I found minimal number of edges which has to be added to make the graph strongly connected (ie. there should be a path from every node to all others)? Does this problem have a name?

Solution 1

It's a really classical graph problem.

1. Run algorithm like Tarjan-SCC algorithm to find all SCCs. Consider each SCC as a new vertice, link a edge between these new vertices according to the origin graph, we can get a new graph. Obviously, the new graph is a Directed Acyclic Graph(DAG).
2. In the DAG, find all vertices whose in-degree is 0, we define them {X}; find all vertices whose out-degree is 0, we define them {Y}.
3. If DAG has only one vertice, the answer is 0; otherwise, the answer is max(|X|, |Y|).

Solution 2

Off the top of my head, it seems the simplest (fewest edges) way to make a directed graph strongly connected would be to just have a cycle involving all nodes; so the minimum number of edges would just be N where N is the number of nodes. If there are already edges, just do something like connect longest existing directed path to the next longest path that doesn't overlap with your current path, until you form a complete cycle (once your path contains all nodes, connect the ends to form the cycle.)

Not sure if there is a more formal definition of any of this, but is seems logical to me.

Solution 3

I would find all weakly connected components, and tie them up in a cycle.

EDIT:

To be more explicit, the idea is if you have WCCs W(1),...,W(n), make all of W(i%n + 1) reachable from any node in W(i), for i=1 to n.

Comments

[Fred Foo]

This is incorrect. Consider the digraph a -> b. That has two SCCs, but one WCC, so your algorithm wouldn't do anything.

[mitchus]

@larsmans In this case it would tie the single WCC up in a cycle, i.e. add the edge b -> a. I will add more detail to make it more explicit.

[Fred Foo]

I'm sorry, but I don't really understand what you mean by this.

[mitchus]

@larsmans Do you disagree with some specific part of the answer? The answer by Jun HU is much better anyway :)

[mitchus]

I am not sure I understand the solution. Consider the graph with edges (a,b),(b,e),(e,b),(a,c),(c,f),(f,c),(b,d),(c,d). The resulting DAG is (A,B),(A,C),(B,D),(C,D), with B={b,e} and C={c,f}. Hence X=Y={B,C} so |X|=|Y|=2. However, clearly, we can just add the single edge (d,a) to the original graph to make it strongly connected.

[mitchus]

With in-degree set to 0, the algorithm fails for the following graph: (a,b),(b,d),(d,b),(a,c),(c,e),(e,c) which results in DAG (A,B),(A,C). There max(|X|,|Y|)=1 but we need two edges to make the graph strongly connected.

[Jun HU]

@mitchus in the new DAG, A's in-degree is 0, B and C has out-degree which is 0. So |X| = 1, |Y| = 2, and answer is 2.

[Sanjit Prasad]

How can we find required minimum edges (any if possible)?