Subgraph with minimum edge weight and node weight> = Val

Question

I ran into this problem. On an undirected graph, each node and edge has weight. All weights are non-negative. If S is specified, find the associated subgraph with the minimum sum of the weights of the edges, so that its sum of the weights of the node is at least S.

The most obvious solution is a brute force approach that takes into account all possible subgraphs. But the time complexity is exponential. Is there a better algorithm for this? My intuition is that we can convert node weights to edge weights, and then apply the spanning tree algorithm. But I could not solve it clearly. How to solve this problem?

EDIT: It looks like I was not clear enough about the description of the subgraph. The selected subgraph should be the only connected component. Hope this is clear now.

Answer 1

I think this problem is NP-hard through shortening from the Steiner tree problem. Given the graph G and the set of nodes S that must be stretched, set the weight of all nodes in S so that one and all other nodes are equal to 0. A subgraph with a node weight of at least | S | with the minimum total cost of the edge there should be a tree (if there are any cycles, removing the edge from the cycle only reduces the cost) and should connect all the nodes that need to be stretched. Therefore, it is a Steiner tree. In general, this reduction can be calculated in polynomial time, so your problem is NP-hard.