0
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

This is already NP-hard in the special case that the graph is a tree, since Knapsack can be reduced to such an instance of this problem: Let $v_i$ be the value of the $i$-th item, and $w_i$ its weight. Create a vertex of weight $v_i$ for each item $i$, and a single extra vertex that is connected by an edge of weight $w_i$ to each item $i$. A capacity-$b$ knapsack can be filled with items of value at least $k$ iff the solution to the constructed instance of your problem with total edge capacity $b$ can achieve a total vertex-value of $k$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.