6
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$
    – FiB
    Mar 29, 2012 at 11:03
  • $\begingroup$ if you are still interested in the question in your comment, it would be better to open a new one. $\endgroup$
    – Artem Kaznatcheev ♦
    Feb 6, 2014 at 15:52

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – FiB
    Mar 28, 2012 at 9:37
  • $\begingroup$ 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. $\endgroup$
    – Janne H. Korhonen
    Mar 28, 2012 at 10:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.