I am considering the following problem.

We are given a Directed Acyclic Graph. In general, there would be some number of subgraphs that, contracted into one node, would make it a tree. For example, in this graph:


If I contract the nodes $b$ and $c$ into a single node, I obtain a tree (quite a trivial one in this case):


In this example, only one subgraph had to be contracted, but in general more than one subgraph can be required. Note that this is not the only possibility, as contracting $c$ and $d$ would have been also fine. Also, trivially the entire graph could be contracted to obtain a trivial tree of a single node, so we have to look for a minimal solution.

So, the problem I am considering is: Given a DAG, find a set of minimal subgraphs which contractions would turn the DAG into a tree.

Is this problem $NP$-hard? Has it got a specific known name?

  • $\begingroup$ No, collapsing (or contracting) means to substitute the nodes with one node, preserving in this new node all the edges pointing to or starting from the collapsed nodes, removing duplicate edges that might form. $\endgroup$ Mar 17, 2016 at 13:24
  • $\begingroup$ I thought it were a fairly standard graph-theoretic concept, sorry if it isn't $\endgroup$ Mar 17, 2016 at 13:24
  • 1
    $\begingroup$ Is the set of minimal subgraphs minimal in the sense of number of nodes, or number of subgraphs? For example, in your case I could pick a single subgraph of the entire dag and compress it into one node. $\endgroup$ Mar 17, 2016 at 14:30
  • 4
    $\begingroup$ Can you specify your problem more formally? You want a partition of the vertices into sets $S_1,\ldots,S_m$ such that after collapsing each $S_i$ into a single vertex $v_i$ what remains is a tree, and some other condition, but I don't understand your other condition. Do you want the partition to be such that no refinement is also a solution? $\endgroup$ Mar 17, 2016 at 18:01
  • 1
    $\begingroup$ You may define the problem clearly, if you are looking for a good answer. Contraction is an operation on edges, which means that the edge becomes a vertex. Merging is defined on a set of vertices, which merges a set of vertices/subgraph into a single vertex, keeping all the edges in their place. Would you formally define you "collapse" operation? $\endgroup$
    – orezvani
    Mar 18, 2016 at 6:57


Your Answer

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

Browse other questions tagged or ask your own question.