Abstract
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.
Users
Please
log in to take part in the discussion (add own reviews or comments).