Subgraph with minimum edge weight and node weight >= Val

Question

I came across this problem - In an undirected graph every node and edge has a weight. All the weights are non-negative. Given a value S, Find the connected subgraph with minimum sum of edge weights such that its sum of node weights is at least S.

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

EDIT : Looks like I was not clear enough about the description of subgraph. The selected subgraph must be a single, connected component. I hope it's clear now.

Answer 1

I think this problem is NP-hard via a reduction from the Steiner tree problem. Given a graph G and a set of nodes S that need to be spanned, set the weight of all of the nodes in S to one and all the other nodes to 0. A subgraph with node weight at least |S| with minimum total edge cost must be a tree (if there are any cycles, deleting an edge from the cycle only decreases the cost) and must connect all of the nodes that need to be spanned. It's therefore a Steiner tree. Overall, this reduction can be computed in polynomial time, so your problem is NP-hard.