<p>This problem is <a href="https://en.wikipedia.org/wiki/Feedback_vertex_set" rel="nofollow noreferrer">Feedback Vertex Set</a> 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).</p>

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

<p>This graph <span class="math-container">$G'$</span> will have the following property: you can map the nodes of <span class="math-container">$G'$</span> to the nodes of <span class="math-container">$G$</span> in a way that bijects the edges of <span class="math-container">$G'$</span> with the edges of <span class="math-container">$G$</span>.  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 <span class="math-container">$s \in S$</span> into the two corresponding nodes in <span class="math-container">$G'$</span>, rerouting edges such that the incoming edges all go to one new copy <span class="math-container">$s_1$</span> and the outgoing edges all go to the other new copy <span class="math-container">$s_2$</span>).</p>

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

CC BY-SA 4.0
2019-10-09T22:36:29.650Z
2019-10-09T22:36:29.650Z
GMB
<p>I have a quite "common" need : making a directed graph (with one or several cycles) a directed <strong>acyclic</strong> graph (DAG).</p>

<p>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. </p>

<p>For exemple, for a graph with such a loop (<code>A &gt; B &gt; C &gt; A</code>) :</p>

<p><a href="https://i.sstatic.net/2Qo8E.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2Qo8E.png" alt="Looping graph"></a></p>

<p>I would like to get a non-looping graph like this one :</p>

<p><a href="https://i.sstatic.net/AoWX6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/AoWX6.png" alt="Non looping graph, with duplicated A node"></a></p>

<p>So here :</p>

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

<p>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 <em>duplicated</em> nodes. I usually work with graphs having less than 100 nodes.</p>

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

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

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

<p>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.</p>

<hr>

<p>Note : this question has also been posted on StackOverflow <a href="https://stackoverflow.com/questions/58287040/breaking-cycles-in-network-graph-by-adding-nodes-and-rerouting-edges">[here]</a></p>

CC BY-SA 4.0
2019-10-08T14:09:21.687Z
The question is not well-defined: it is unclear how the transformed graph should relate to the given one.
Radu GRIGore
CC BY-SA 4.0
2019-10-08T14:33:15.277Z
Edited to detail the transformation process
Arkeen
CC BY-SA 4.0
2019-10-08T19:43:49.893Z
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
CC BY-SA 4.0
2019-10-11T12:33:51.590Z
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
CC BY-SA 4.0
2019-10-11T22:29:01.643Z
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
CC BY-SA 4.0
2019-10-14T10:11:00.850Z
Well, the "rule" for A' > D (and for all outgoing arcs from new nodes) is that since A has an outgoing edge to D, A' should also have it. But A' > B should not be duplicated, since it would create a new cycle.
I also realise I clearly should have mentionned that in the first place, but the aim of all this is to be able to order nodes (using Kahn or DFS).
Arkeen
CC BY-SA 4.0
2019-10-15T14:57:22.407Z
I'm sorry, but I don't find that to clarify anything. It was already clear that in this example you add A'->D to because the original had A->D, and you don't add A'->B because that would give a cycle. The problem, however, is that *that* is very far from being a precise rule that would work for all input graphs. I'm voting to close as unclear. It is *sets* of arcs that introduce or not cycles, so you cannot in general decide on per-arc basis whether to include it using the cycle rule.
Radu GRIGore
<graph-theory><directed-acyclic-graph>
Breaking cycles in network graph by adding nodes and rerouting edges
Arkeen
# Breaking cycles in network graph by adding nodes and rerouting edges

(Asked by: username_0 on 2019-10-08)

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`) :

[![Looping graph](https://i.sstatic.net/2Qo8E.png)](https://i.sstatic.net/2Qo8E.png)

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

[![Non looping graph, with duplicated A node](https://i.sstatic.net/AoWX6.png)](https://i.sstatic.net/AoWX6.png)

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]](https://stackoverflow.com/questions/58287040/breaking-cycles-in-network-graph-by-adding-nodes-and-rerouting-edges)

**Tags:** graph-theory, directed-acyclic-graph
> **Comments:**
> **username_1**: The question is not well-defined: it is unclear how the transformed graph should relate to the given one.  
> **username_0**: Edited to detail the transformation process  
> **username_2**: 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.  
> **username_1**: 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?  
> **username_2**: 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.  
> **username_0**: Well, the "rule" for A' > D (and for all outgoing arcs from new nodes) is that since A has an outgoing edge to D, A' should also have it. But A' > B should not be duplicated, since it would create a new cycle. I also realise I clearly should have mentionned that in the first place, but the aim of all this is to be able to order nodes (using Kahn or DFS).  
> **username_1**: I'm sorry, but I don't find that to clarify anything. It was already clear that in this example you add A'->D to because the original had A->D, and you don't add A'->B because that would give a cycle. The problem, however, is that *that* is very far from being a precise rule that would work for all input graphs. I'm voting to close as unclear. It is *sets* of arcs that introduce or not cycles, so you cannot in general decide on per-arc basis whether to include it using the cycle rule.  

---

## 1 answers

### Answer by username_2 on 2019-10-09. Score: 3

This problem is [Feedback Vertex Set](https://en.wikipedia.org/wiki/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'$.


---

