The Densest Subgraph Problem with a Convex/Concave Size Function

Yasushi Kawase, Atsushi Miyauchi

In the densest subgraph problem, given an edge-weighted undirected graph $G=(V,E,w)$, we are asked to find $S\subseteq V$ that maximizes the density, i.e., $w(S)/|S|$, where $w(S)$…