# Complexity of the directed Steiner tree problem on special graph classes

I am interested in the complexity of the directed Steiner tree problem: Given a weighted digraph $D=(V,E)$, a root $r\in V$ of $D$, and a set of terminals $T\subseteq V$. The objective is to find a minimum cost arborescence of $D$ rooted at $r$, in which there is a path from $r$ to each node in $T$.

Is a polynomial time algorithm known if the input is restricted to digraphs whose underlying undirected graph is a series-parallel graph (or equivalently is a $K_4$-free graph or is a partial $2$-tree or has treewidth at most $2$)?

• @Janne Korhonens answer suggests that it might be possible to solve the problem in polynomial time on digraphs which underlying undirected graph is of bounded treewidth. I'd like to broaden my question to those graphs. Should I edit the question or is it better practice to open a new question? At this point I can imagine that the problem is tractable on series-parallel graphs but I am sceptic if it is on digraphs whose underlying undirected graph is of bounded treewidth. – FiB Mar 29 '12 at 11:03
• if you are still interested in the question in your comment, it would be better to open a new one. – Artem Kaznatcheev Feb 6 '14 at 15:52

This manuscript seems to prove exactly that. (It doesn't; the complexity parameter is $|T|$, not the treewidth.)
EDIT: The undirected Steiner tree is, on the other hand, known to be fixed-parameter tractable with regards to parameter $w$ the treewidth of the underlying graph. My suggestion would be to try and adapt this algorithm to the directed case, which would in particular give a polynomial time algorithm for series-parallel graphs.