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.

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

The Dense Subgraph Problem (thanks @PalGD) is a special case of the above problem--with no node weights and unit edge weights. See the solutions for the dense subgraph problem here. These solutions (LP and 2-approximation Greedy) easily generalize to the above problem (generalizing LP requires a bit of understanding/effort, but generalizing Greedy is trivial).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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