1
$\begingroup$

This is an exercice is Rolf Niedermeier's book "Invitation to fixed-parameter algorithms", Chapter 13.

Show that the following problem is W[1]-hard: Steiner Tree in Graphs with respect to the parameter "number of non-terminal vertices".

The way I understand it, if there are most $k$ non-terminal vertices, then this doesn't help in solving the Steiner problem in time $f(k)n^c$.

The objective is to find the minimum number of edges connecting terminal vertices (while some vertices are non-terminal). I can't find a reduction however. I am convinced that the parameter $k$ being number of included non-terminal vertices in a solution makes it W[2]-hard. But if $k$ is the number of existing non-terminal vertices, I don't know. Proof ideas or references will be appreciated.

$\endgroup$
1
  • $\begingroup$ I don't think "Steiner vertex" and "Non-terminal vertex" are the same. A non-terminal vertex is not necessarily a steiner vertex (since you may choose not to include a given non-terminal vertex in the solution). $\endgroup$ Aug 2, 2016 at 18:33

1 Answer 1

1
$\begingroup$

When parameterized by number of non-terminal vertices in the input graph, Steiner Tree is FPT by brute force. ​ - ​ Find a minimum-size subset of non-terminal vertices such that [the subgraph induced by the union of [the set of terminal vertices] with [the chosen set of non-terminal vertices]] is connected, and then output any spanning tree of that subgraph.

(If that's not your interpretation of the problem, then clarify your last paragraph.)

$\endgroup$
1
  • $\begingroup$ Yes, thanks for the answer. That's the correct interpretation and that's what I thought - but I needed some confirmation. The author probably meant W[1]-hard in the number of non-terminal vertices included in a solution. $\endgroup$ Aug 2, 2016 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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