0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Almost done. Required nodes=I, Steiner nodes=$S_i$ and the root. $\endgroup$ – Bangye Feb 28 '14 at 13:35
  • $\begingroup$ I'm actually unsure of what a Steiner node is. Are you saying that the G' or required nodes for an answer yes in St should be what you stated? If so then you would just get weight equal to the number of subsets in S. I am probably misinterpreting what you are saying completely $\endgroup$ – Tolon Feb 28 '14 at 15:31
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.