  The bootstrap percolation (or threshold model) is a dynamic process modelling
the propagation of an epidemic on a graph, where inactive vertices become
active if their number of active neighbours reach some threshold. We study an
optimization problem related to it, namely the determination of the minimal
number of active sites in an initial configuration that leads to the activation
of the whole graph under this dynamics, with and without a constraint on the
time needed for the complete activation. This problem encompasses in special
cases many extremal characteristics of graphs like their independence,
decycling or domination number, and can also be seen as a packing problem of
repulsive particles. We use the cavity method (including the effects of replica
symmetry breaking), an heuristic technique of statistical mechanics many
predictions of which have been confirmed rigorously in the recent years. We
have obtained in this way several quantitative conjectures on the size of
minimal contagious sets in large random regular graphs, the most striking being
that 5-regular random graph with a threshold of activation of 3 (resp.
6-regular with threshold 4) have contagious sets containing a fraction 1/6
(resp. 1/4) of the total number of vertices. Equivalently these numbers are the
minimal fraction of vertices that have to be removed from a 5-regular (resp.
6-regular) random graph to destroy its 3-core. We also investigated Survey
Propagation like algorithmic procedures for solving this optimization problem
on single instances of random regular graphs.
