Planted vertex cover problem on regular random graphs and nonmonotonic temperature-dependence in the supercooled region

Xin-Yi Fan, Hai-Jun Zhou

We introduce a planted vertex cover problem on regular random graphs and study it by the cavity method of statistical mechanics. Different from conventional Ising models, the equil…