Breaking cycles in network graph by adding nodes and rerouting edges I have a quite "common" need : making a directed graph (with one or several cycles) a directed acyclic graph (DAG).

But the way I want to achieve it is, I guess, way more specific : I would like to break cycles by duplicating nodes, and rerouting edges. 

For exemple, for a graph with such a loop (A &gt; B &gt; C &gt; A) :



I would like to get a non-looping graph like this one :



So here :


A new node A' has been created (duplicated from A) 
The edge C &gt; A has been deleted, replaced by C &gt; A' 
Another edge A' &gt; D is also created, to preserve "adjacency": it was possible to go from B to D in the first graph, so I want this to be possible in the transformed graph too.


The case above may appear quite simple, but I am tryig to build an automated method to do that. I also have some cases with interwined cycles, which are way more complex to deal with. Finally, I aim to minimise the number of duplicated nodes. I usually work with graphs having less than 100 nodes.

The aim of all this is to be able to order nodes (using Kahn or DFS). 


In the exemple above, A &gt; B &gt; C &gt; A' &gt; D seems the most intuitive order. 
A &gt; D &gt; B &gt; C &gt; A' would also be a valid order, but I think it is less intuitive. 


This is also the reason for keeping the original A &gt; D arc, forcing the resulting order to be the first one mentionned above.

Any leads about how to do that ? Any existing methods or scripts (preferably python) ? 
During my research, I have never found any information about such a way to break cycles, maybe I have not searched enough, or maybe not in the good direction.



Note : this question has also been posted on StackOverflow [here]
This problem is Feedback Vertex Set in disguise, and hence NP-Hard, but I'd imagine there are good heuristics out there (I don't know the references myself, maybe someone can help me out here).

More specifically, for an input graph $G = (V, E)$ with minimal FVS $S \subseteq V$, there is a solution to your problem that copies each member of $S$ once (and no other nodes are copied at all), and this is best possible.  That solution is as follows.  Define the nodes of $G'$ in the following order: first we put all the nodes in $S$ (in any order), then we put the nodes of $V \setminus S$ in topological order in the DAG $G \setminus S$, and finally we put another identical copy of the nodes of $S$ (again in any order).  The edges $(u, v) \in E$ are placed in $G'$ in the natural way: if either endpoint $u, v \notin S$ then there is only one way to place the edge in $G'$, and if both $u, v \in S$ then in $G'$ the corresponding edge goes from the first copy of $u$ to the last copy of $v$.

This graph $G'$ will have the following property: you can map the nodes of $G'$ to the nodes of $G$ in a way that bijects the edges of $G'$ with the edges of $G$.  I believe this is the right way to formalize the node-splitting process you are describing (in the node-splitting view, you would iteratively split each node $s \in S$ into the two corresponding nodes in $G'$, rerouting edges such that the incoming edges all go to one new copy $s_1$ and the outgoing edges all go to the other new copy $s_2$).

Additionally, if $G$ has $n$ nodes then $G'$ has $n + |S|$ nodes, but there is no graph $G''$ on $n + |S| - 1$ nodes with the above property.
That is because, if one can split a set of nodes $S$ to reach a DAG, then surely one also has a DAG by deleting $S$ entirely.  So the size of a minimal FVS is no more than the number of extra nodes required in $G'$.