# W[1]-hardness of Steiner tree w.r.t. number of non-terminal vertices

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.

• 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). Aug 2, 2016 at 18:33