World's most popular travel blog for travel bloggers.

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

, , No Comments
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.

Asked By : Manuel Lafond
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.)

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback