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:

DAG

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

Collapsed

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?

  • 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. – gigabytes Mar 17 '16 at 13:24
  • I thought it were a fairly standard graph-theoretic concept, sorry if it isn't – gigabytes Mar 17 '16 at 13:24
  • 1
    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. – Kurt Mueller Mar 17 '16 at 14:30
  • 4
    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? – Yuval Filmus Mar 17 '16 at 18:01
  • 1
    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? – orezvani Mar 18 '16 at 6:57

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.