# Maximum weighted subgraph

Problem: Given a graph G with positive integral weights on nodes as well as edges, find an induced subgraph H with maximum total weight per node, i.e., the goal is to maximize $$\frac{ \sum_{e \in H}w(e) + \sum_{v \in H} w(v) }{|V(H)|}.$$

If you allow negative weights, then it is NP-hard (easy reduction from Clique). I have a strong feeling that the above is not NP-Hard.

I would love to have some first-thoughts on the above, if not a full-fledged optimal algorithm. Does it seem to be NP-Hard? What is the closest known problem -- my thoughts were Prize Collection, Clique -- but both seem much harder.

• Isn't G the induced subgraph of G with maximal weight? – qz- Apr 19 at 19:16
• @qz no, you want the subgraph that maximizes average weight (... so to speak) – Pål GD Apr 19 at 19:21
• Have a look at the Dense Subgraph Problem. – Pål GD Apr 19 at 19:27
• @PålGD ah, thanks for editing the question to be more clear – qz- Apr 19 at 19:30
• Yes, I see that "dense subgraph problem" is very close. Thanks -- that should work. – Brian Apr 19 at 20:17