pdf icon
Volume 11 (2015) Article 13 pp. 339-355
Computing the Partition Function for Cliques in a Graph
Received: June 24, 2014
Revised: February 17, 2015
Published: December 4, 2015
Download article from ToC site:
[PDF (247K)]    [PS (1057K)]    [PS.GZ (278K)]
[Source ZIP]
Keywords: algorithm, clique, partition function, subgraph density, graph
ACM Classification: F.2.1, G.1.2, G.2.2, I.1.2
AMS Classification: 68Q17, 52C07, 11H06, 11H31, 05B40

Abstract: [Plain Text Version]

We present a deterministic algorithm which, given a graph $G$ with $n$ vertices and an integer $1 < m \leq n$, computes in $n^{O(\ln m)}$ time the sum of weights $w(S)$ over all $m$-subsets $S$ of the set of vertices of $G$, where $w(S)=\exp\{\gamma m \sigma(S) +O({1}/{m})\}$ provided exactly $\binom{m}{2}\sigma(S)$ pairs of vertices of $S$ span an edge of $G$ for some $0 \leq \sigma(S) \leq 1$, and $\gamma > 0$ is an absolute constant. This allows us to tell apart the graphs that do not have $m$-subsets of high density from the graphs that have sufficiently many $m$-subsets of high density, even when the probability to hit such a subset at random is exponentially small in $m$.