How to minimally extend a digraph such that all nodes are on a cycle?

Question

Let's say we have a directed graph with $n$ nodes and $m$ edges. For each node we want to make path that will start from this node, possibly traverse some other nodes and finish in the same node, in other words we want to make a cycle through each node. It is allowed to add edges that start and finish in the same node.

We want to use minimum number of edges.

Let's for example consider the following graph. We can add edges: $(1,1),(2,2),(3,3),(4,4)$. But that will cost us to add 4 edges, and we can make the cycles with adding only one edge $(4,1)$.

I think that first we should find all the paths in the graph, and then link the last node with the first node, this will allow us to minimize the added edges, and surely will make all the nodes in the path linked in the cycle.

But the problem is find all the paths, I cannot think of the algorithm that will find us all pairs of paths, also the problem is if there is more than one path between the first and the last nodes, please give me some hints on how to solve this problem.

Also, I think that finding all paths in the graph is $NP-hard$ and it may be really slow, but the number of nodes is small, less than 20, so even solution of time complexity $O(2^N)$ are good.

Answer 1

• Find all the strongly connected components (SCC) of the original graph.
• Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
• Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
• Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
• Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph provided that the original graph is connected. Your requirement to have all the nodes belonged to some cycle is more weak - for example, a set of SCC's, not connected at all or connected by single edges, satisfies your goal definition.

However, it's unclear if this more weak requirement will allow you to decrease the number of additional edges compared to the number of additional edges, given by the algorithm, described here.