0
$\begingroup$

We've been given a weighted graph with marked nodes. We want to make a minimum-weight subtree from this graph that contains all marked nodes.

I want to show that this problem is NP-hard. Is there any idea to which problem is the best for reduction to this problem?

$\endgroup$
  • 1
    $\begingroup$ One that works fairly easily is exact cover by 3 sets (X3C). $\endgroup$ – Juho Nov 20 '14 at 13:14
  • $\begingroup$ See our reference questions for general hints. If you want further help, please include what you have tried and where you did get stuck. $\endgroup$ – Raphael Nov 20 '14 at 17:32
2
$\begingroup$

This is the problem of finding a Steiner tree in the graph. It's one of the NP-complete problems in Karp's original paper; the reduction there is from Exact cover by 3-sets.

$\endgroup$
0
$\begingroup$

I think vertex cover can be easily used when we consider edges as nodes and mark only those nodes that has a correspend edge in G. I think it will work

$\endgroup$
0
$\begingroup$

You can use reduction using Dominating set.

Given an input $G$ and $k$ for Dominating set, you create a new graph with a root node. Create a node for each node in the original graph. Connect the root node with each node by edge of cost 1. Connect each node with each other with edge of cost 0 if they are connected in the original graph. Make all the nodes as marked. The weight for the decision version will be $k$ (the set size in the input).

If there is a tree that covers all marked nodes, then we look at all the edges of weight 1 that come from the root. The nodes (other than the root) of these edges are the dominating set of size k in the original input. This is because the tree covers all nodes, so all nodes in the original graph connect with the resulting dominating set of size $k$ that we found.

The other direction is also straight-forward. We select the nodes that are in the dominating set of size $k$ and connect them with the root. All other nodes must be connect with this tree because these $k$ nodes form a dominating set. Because there are $k$ nodes connecting with the root so the weight of the tree is $k$.

The problem is also in NP because one can verify coverage and weight easily. So the problem is NP-complete overall.

$\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.