Densest subgraph variation
Let be a graph. Consider an edge weight function and a vertex cost function .
We are interested in finding , such that is maximized.
This is very close to the densest subgraph problem, as it is basically the Lagrangian relaxation of the problem.
This problem is equivalent to a min--cut computation on a suitable graph. Indeed, minimizing is equivalent to minimizing . This can be solved easily by modeling it as a min--cut.