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?
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.
