Some spin glass ideas applied to the clique problem

Abstract

In this paper we introduce a new algorithm to study some NP-complete problems. This algorithm is a Markov Chain Monte Carlo (MCMC) inspired by the cavity method developed in the study of spin glass. We will focus on the maximum clique problem and we will compare this new algorithm with several standard algorithms on some DIMACS benchmark graphs and on random graphs. The performances of the new algorithm are quite surprising. Our effort in this paper is to be clear as well to those readers who are not in the field.

21 pages, latex file

References in corpus (1)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm

Cited by in corpus (7)

• Finding One Community in a Sparse Graph
• Metastable states, quasi-stationary distributions and soft measures
• Equilibrium and non-equilibrium Ising models by means of PCA
• Probabilistic Cellular Automata for low temperature Ising model
• Phase transitions for the cavity approach to the clique problem on random graphs
• Gaussian Mean Fields Lattice Gas
• Sampling the Fermi statistics and other conditional product measures