I have an unweighted directed graph $(V, E)$ and a subset $T \subseteq V$ of these vertices. I want to find the minimum tree $(V',E')$ that contains all these $T$ vertices (minimize in number of nodes $|V'|$).

In my problem all vertices $t \in T$ have no leaving edges: $$\left\{(t,w) \in E \mid t \in T\right\}=\emptyset$$

This is a specific case of the Directed Steiner Tree problem.

What's the best algorithm and it's complexity to find the exact solution to the Directed Steiner Tree problem? (Or, if there is, a better solutions to this specific case of the Directed Steiner Tree)

What are the most used approximations for this problem?

  • $\begingroup$ I am looking for this same thing. I would just consider that there could actually be more than one minimal tree. In my case I need a unique answer so I only need to know the unique tree or that there is not such tree. Have you found anything? I'm almost sure I have a solution. But It's still in rough form. Could you expand on what you mean by leaving edges? $\endgroup$ Jun 24 '16 at 19:08
  • $\begingroup$ In my case, all nodes $t\in T$ had no output edges. I didn't find anything specific. Since the graph I was working on was small enough, I searched all possible trees in the graph in growing order, until I found one that contained T. $\endgroup$
    – t.pimentel
    Jun 24 '16 at 19:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.