Reduction from Steiner tree to minimum set cover

Question

I am trying to teach myself complexity. I am trying to come up with a reduction from minimum set cover (given a set of items $I$, and a set $S$ of subsets of $I$ and an integer $k$, is there a subset $S'$ of $S$ such that $|S'|\leq k$ and $union(S')=I$) to weighted Steiner tree (given a graph $G=(V, E)$, a weight function $w$, a subset $V'$ of $V$ and integer $k>0$, is there a subtree $G'$ of $G$ such that the sum of the weight of the edges in $G'\leq k$ and $V'$ is contained in $G'$?) , but have gotten a bit stuck. I believe I am on the right path.

Here's what I have so far. Given an instance of minimum set cover, define a root node r, For every subset in $S_i\in S$, define a node $S_i$ and connect it by an edge to $r$ with weight one. For every element in $S_i$, define a node and connect them to $S_i$ via an edge of weight 0. This creates a tree. I believe something like this should work, but I cannot figure out how to define $G'$ for the constructed instance of STG such that there is an answer yes if there is a minimum set cover.

Any help would be greatly appreciated, thanks

Answer 1

It is your definition of Steiner tree problem that causes the difficulty here.

Your definition does not include the set of terminals $S\subseteq V(G)$. Then, a Steiner tree is a subtree $G'$ of the graph $G$ that spans $S$.

Keep this definition in mind, you can now move on to reduce $\mathrm{EXACT}$-$\mathrm{COVER}$-$\mathrm{BY}$-$3$-$\mathrm{SET}$ to your problem. The set of terminals would be the set of items to be covered, plus the root $r$. The construction is exactly your construction including your weight function.

But, the required weight $k$ is now $|U|/3$ where $U$ is the universe of items to be covered.

---

Clearly, a Steiner tree that spans $r$ and the whole universe should be a tree that can be rooted at $r$ with $k$ children as the set cover solution. Note that a Steiner tree is by no mean a rooted one but here we see that being seen as rooted at $r$ does help.

Answer 2

Although it's not actually necessary to get a reduction here, you should always keep the threshold parameters of the two problems separate, because they don't need to be equal. That is, give different names to the threshold parameter of the Minimum Set Cover instance you are taking as input (let's continue calling this $k$) and the threshold parameter of the Steiner Tree in Graphs instance you are constructing (let's call this $k'$). This gives you more flexibility.

Here this allows you to get a stronger result: Even Steiner Tree in unweighted Graphs is NP-complete. Hint:

Try setting every edge in $G'$ to have weight 1.