Reduction from Steiner tree to minimum set cover 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&gt;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
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.