The Art Gallery Guardian

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.

Posted by Chao Xu on .
Tags: combinatorial optimization.