Similar questions were asked elsewhere, but no satisfying answers occurred yet.
In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is bounded and the sum of internal vertex weights is maximum. Is this problem NP-hard? Please note that the subgraph has to be connected, and the sum of internal edge weights is calculated by the weight of Minimal Spanning Tree of this subgraph. An example is shown in attached.
Attention: previously someone suggested that we can set the bound to 0 to reduce the problem to Maximum Independent Set. However, by setting all the bound to 0, the problem should be reduced to finding the node with maximum weight, for the nodes in the independent set are not connected which would cost infinite cost.