# Densest subgraph variation

Let $G=(V,E)$ be a graph. Consider an edge weight function $w:E→R_{+}$ and a vertex cost function $c:V→R_{+}$.

We are interested in finding $S⊂V$, such that $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-$st$-cut computation on a suitable graph. Indeed, minimizing $w(E(S))−c(S)$ is equivalent to minimizing $c(S)+21 w(E(S,Sˉ))+21 ∑_{v∈Sˉ}g(v)$. This can be solved easily by modeling it as a min-$st$-cut.