1
$\begingroup$

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

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

Non looping graph, with duplicated A node

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]

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ The question is not well-defined: it is unclear how the transformed graph should relate to the given one. $\endgroup$
    – Radu GRIGore
    Commented Oct 8, 2019 at 14:09
  • $\begingroup$ Edited to detail the transformation process $\endgroup$
    – Arkeen
    Commented Oct 8, 2019 at 14:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – GMB
    Commented Oct 8, 2019 at 19:43
  • 2
    $\begingroup$ 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? $\endgroup$
    – Radu GRIGore
    Commented Oct 11, 2019 at 12:33
  • 1
    $\begingroup$ 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. $\endgroup$
    – Radu GRIGore
    Commented Oct 15, 2019 at 14:57

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.