The Art Gallery Guardian

Densest subgraph variation

Let G=(V,E)G=(V,E) be a graph. Consider an edge weight function w:ER+w:E\to \R^+ and a vertex cost function c:VR+c:V\to \R^+.

We are interested in finding SVS\subset V, such that w(E(S))c(S)w(E(S))-c(S) 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-stst-cut computation on a suitable graph. Indeed, minimizing w(E(S))c(S)w(E(S))-c(S) is equivalent to minimizing c(S)+12w(E(S,Sˉ))+12vSˉdeg(v)c(S) + \frac{1}{2} w(E(S,\bar{S})) + \frac{1}{2} \sum_{v\in \bar{S}} \deg(v). This can be solved easily by modeling it as a min-stst-cut.

Posted by Chao Xu on 2019-03-24.
Tags: combinatorial optimization.