Given a (positively) weighted directed graph G, a set of query nodes T and a root r, finding the minimum steiner arborescence containing the query nodes and rooted at r is an NP-hard problem
However, I'm having troubles finding a clearly explained approximation algorithm for this problem. This is quite unlike the undirected version of finding a minimum steiner tree, where the (general) 2-approximation algorithm is quite clear .
Does anybody know how to tackle the directed version? What is the state of the art in terms of approximations? Can't find much about it on the web.
Thanks!
The problem is approximable within approximation ratio $O(|S|^\epsilon)$ for every $\epsilon > 0$. For every fixed $\epsilon > 0$ cannot be approximated within ratio $\log^{2-\epsilon} n$, unless $NP \subseteq ZTIME(n^{polylog(n)})$.
See problem 1.2 and bibliography here: http://theory.cs.uni-bonn.de/info5/steinerkompendium/netcompendium.pdf