# Show that finding a minimum-weight subgraph that includes all marked nodes is NP-hard

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?

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

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.

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

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.