# 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 > B > C > A) :

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

So here :

1. A new node A' has been created (duplicated from A)
2. The edge C > A has been deleted, replaced by C > A'
3. Another edge A' > 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 > B > C > A' > D seems the most intuitive order.
• A > D > B > C > A' would also be a valid order, but I think it is less intuitive.

This is also the reason for keeping the original A > 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]

• The question is not well-defined: it is unclear how the transformed graph should relate to the given one. – Radu GRIGore Oct 8 at 14:09
• Edited to detail the transformation process – Arkeen Oct 8 at 14:33
• If it helps you search, the transformation you are describing is a (reverse) homomorphism. Your question is: given a directed graph G, find the DAG G' with the fewest possible nodes so that there is a homomorphism G' --> G. – GMB Oct 8 at 19:43
• Arkeen, the details you added were already clear -- that's not the issue. @GMB: In your formulation, you can always pick G' to be the empty graph. To rule that out, one can require a covering map rather than a homomorphism. But, then, what forces you to add the arc A'->D, in the example given? What exactly is the rule for adding outgoing arcs from new nodes? – Radu GRIGore Oct 11 at 12:33
• Ahh, good catch, you're right of course. My answer below uses the covering-map formulation, but yeah, I think we need OP to clarify the A' --> D rule. – GMB Oct 11 at 22:29

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'$$.