World's most popular travel blog for travel bloggers.

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

, ,
Problem Detail:

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.

###### Answered By : Ricky Demer

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.)