<p><strike><a href="http://www.imsc.res.in/~vraman/pub/cfvs.pdf" rel="nofollow">This manuscript</a> seems to prove exactly that.</strike> (It doesn't; the complexity parameter is $|T|$, not the treewidth.)</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Tree_decomposition" rel="nofollow">tree-decomposition</a> machinery<strike>, which is also used in the linked paper</strike>.</p>

<p>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.</p>

CC BY-SA 3.0
2012-03-28T09:37:38.120Z
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?
FiB
CC BY-SA 3.0
2012-03-28T10:26:22.793Z
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.
Janne H. Korhonen
CC BY-SA 3.0
2012-03-27T19:21:02.820Z
2012-03-28T10:38:17.040Z
2012-03-28T10:38:17.040Z
Janne H. Korhonen
<p>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$.</p>

<p>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$)?</p>

CC BY-SA 3.0
2012-03-29T11:03:32.933Z
@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
CC BY-SA 3.0
2014-02-06T15:52:27.120Z
if you are still interested in the question in your comment, it would be better to open a new one.
Artem Kaznatcheev
<ds.algorithms><graph-theory><graph-algorithms><time-complexity>
Complexity of the directed Steiner tree problem on special graph classes
FiB
# Complexity of the directed Steiner tree problem on special graph classes

(Asked by: username_0 on 2012-03-27)

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, time-complexity

> **Comments:**
> **username_0**: @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.  
> **username_1**: if you are still interested in the question in your comment, it would be better to open a new one.  

---

## 1 answers

### Answer by username_2 on 2012-03-27. Score: 2

[This manuscript](http://www.imsc.res.in/~vraman/pub/cfvs.pdf) 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](http://en.wikipedia.org/wiki/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.

> **Comments:**
> **username_0**: 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?  
> **username_2**: 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.  

---

