Complexity of the directed Steiner tree problem on special graph classes

Question

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ドル$)?

• FiB: @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.
• Artem Kaznatcheev: if you are still interested in the question in your comment, it would be better to open a new one.

Answer 1

(削除) This manuscript seems to prove exactly that. (削除ここまで) (It doesn't; the complexity parameter is $|T|,ドル not the treewidth.)

In general, most NP-hard optimisation problems have polynomial-time algorithms when the input is restricted to bounded-treewidth graphs. These algorithms use the rather well-known tree-decomposition machinery(削除) , which is also used in the linked paper (削除ここまで).

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.

• FiB: Thank you very much for your answer. But I am not convinced: In paragraph 3.1, Lemma 2 it says that the directed STP is in FPT for general graphs. Paragraph 4 does not use the directed STP at all. Is there a reduction I don't see? Regarding treewidth of the underlying undirected graph: It is not immediately useful for directed graphs. DAGs can have quite high (such) treewidth, but are easy instances for many problems. Question is: Are there hard instances which have small treewidth on the other hand?
• Janne H. Korhonen: Oops, the parameter in the Lemma 2 is indeed the size of the terminal set, not the treewidth of the underlying graph. That's what you get for posting late at night. I'll edit my answer.