Testing for Dense Subsets in a Graph via the Partition Function
Alexander I. Barvinok, Anthony Della Pella · SIAM Journal on Discrete Mathematics · 2020
For a set S of vertices of a graph G, we define its density 0 łeq \sigma(S) łeq 1 as the ratio of the number of edges of G spanned by the vertices of S to \binom|S|2. We show that, given a graph G with n vertices and an integer m łl n, the partition function \sum_S \exp\ \gamma m \sigma(S) \, where the sum is taken over all m-subsets S of vertices and 0 < \gamma <1 is fixed in advance, can be approximated within relative error 0 < \epsilon < 1 in quasi-polynomial n^O(łn m - łn \epsilon) time. We discuss numerical experiments and observe that for the random graph G(n, 1/2) one can afford a much larger \gamma, provided the ratio n/m is sufficiently large.