I'm considering the following problem.Consider a Directed Acyclic Graph. In general, there would be some number of subgraphs that, collapsed into one node, would make it a tree. For example, in this graph:If I collapse 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 collapsed, but in general more than one subgraph can be required. Note that this is not the only possibility, as collapsing $c$ and $d$ would have been ok, too. Also, trivially the entire graph could be collapsed to obtain a trivial tree of a single node, so we have to look to a minimal solution.So the problem I'm considering is: Given a DAG, to find a set of minimal subgraphs, that collapsed would turn it into a tree.Is this problem $NP$-hard? Has it got a specific known name?
Has this graph-theoretic problem got a known name? Is it NP-hard?
graphs;trees;np hard;dag