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

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.

• Your example graph is acyclic - do you consider only such kind of graphs? If yes, look at their sources and sinks – HEKTO Feb 4 '18 at 21:29
• No, the give graph in the beginning may have cycles already, but if there are not nodes that are in cycle, we should still add edges. – someone12321 Feb 4 '18 at 21:42
• Can you clarify the problem statement? Do you want all nodes to be on a cycle, or all edges? The minimal solutions for these cases may be different. For instance, in the graph with nodes a, b and edges (a,a), (a,b), (b,b), all nodes are on a cycle, but not all edges are. – reinierpost Feb 9 '18 at 9:30
• All nodes should be part of cycle, or in other words: for each node there should be path that starts and finish in this node – someone12321 Feb 9 '18 at 10:53
• So adding a self-loop on each node would satisfy this requirement? (Except that it may not be minimal.) – reinierpost Feb 9 '18 at 16:33

• 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.

• Let's say if we have only one source, then the edges needed to be added are the edges from the source to the sinks. But if we have more than one source we want to connect the sources between each other as in the example graph by D.W. What would be the most optimal algorithm to connect the sources between each other. – someone12321 Feb 8 '18 at 7:10
• No, you don't need to add edges between sources - you need only edges from sinks to sources. You can use the Raghavan algorithm, but I think it's not supposed to work on disconnected graphs (like @D.W. example, removed for some reason now). – HEKTO Feb 8 '18 at 18:17
• Another point, the definition "to be part of cycle" should be rewritten in form: for each node there should be path that starts and finish in this node – someone12321 Feb 8 '18 at 21:20
• I don't see any difference - can you please elaborate? – HEKTO Feb 8 '18 at 21:24
• Disconnected graphs are not a problem: just leave them disconnected! – reinierpost Feb 9 '18 at 9:32