patternMinor
Minimal Steiner Tree in unweighted directed graph
Viewed 0 times
steinergraphunweighteddirectedminimaltree
Problem
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?
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?
Solution
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.
https://scipjack.zib.de/
Should give you an optimal solution to problems even with order 10000 arcs within minutes.
Context
StackExchange Computer Science Q#56800, answer score: 2
Revisions (0)
No revisions yet.