6
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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$
    – Arturo Hernandez
    Jun 24, 2016 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, 2016 at 19:42

1 Answer 1

Reset to default
2
$\begingroup$

This problem is still NP-hard. You can reduce the (NP-hard) unweighted, undirected Steiner tree problem to the directed one by replacing each edge by two anti-parallel arcs. You can reduce any unweighted directed Steiner tree problem to the problem that you describe by adding for each terminal t other than the root a terminal t' and an arc (t,t'). The directed Steiner tree problem is also hard to approximate, see, e.g., "Polylogarithmic inapproximability" by E. Halperin and R. Krauthgamer. However, if you look for a fast practical algorithm to get an optimal solution, the probably best option is this one: https://scipjack.zib.de/ Should give you an optimal solution to problems even with order 10000 arcs within minutes.

Improve this answer
$\endgroup$

Your Answer

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

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