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$)?
Complexity of the directed Steiner tree problem on special graph classes
ds.algorithms;graph theory;graph algorithms;time complexity