"Some spin glass ideas applied to the clique problem"

We face the clique problem, i.e., the study of the maximal complete subgraph of a given graph $G$, by using ideas inspired by the cavity method introduced in spin glass theory. To this purpose we introduce an algorithm, which is sufficiently simple so that its behavior can be studied at least on random graphs providing some explanation of the difficulty of the problem. The algorithm is actually a Markov Chain Monte Carlo (MCMC), whose stationary measure is concentrated, for low temperature, on the cliques of the graph. The two particular features of this approach are the fact that the evolution can be thought as a probabilistic cellular automaton with mean field interaction, and therefore the configuration of the system may change completely even in a single step, and the fact that the dynamics is conservative. The algorithm has been tested on random graphs and on DIMACS benchmarks, with very good numerical results, also on large graphs. The rigorous study of the mixing time of the chain is still open.