Searching for dense subsets in a graph via the partition function

For a set $S$ of vertices of a graph $G$, we define its density $0 \leq \sigma(S) \leq 1$astheratioofthenumberofedgesof$G$ spanned by the vertices of $S$ to $\left(\genfrac{}{}{0px}{}{\mathrm{\mid }S\mathrm{\mid }}{2}\right)$. We show that, given a graph $G$ with $n$ vertices and an integer $m$, the partition function $\sum_S \exp{ \gamma m \sigma(S) }$,wherethesumistakenoverall$m$-subsets$S$ofverticesand$0 < \gamma <1$isfixedinadvance,canbeapproximatedwithinrelativeerror$0 < \epsilon < 1$inquasi-polynomial$n^{O(\ln m - \ln \epsilon)}$ time. We discuss numerical experiments and observe that for the random graph $G(n,1\mathrm{/}2)$ one can afford a much larger $\gamma$, provided the ratio $n\mathrm{/}m$ is sufficiently large.