  We introduce a planted vertex cover problem on regular random graphs and
study it by the cavity method. The equilibrium ordering phase transition of
this binary-spin two-body interaction system is discontinuous in nature
distinct from the continuous one of conventional Ising-like models, and it is
dynamically blocked by an extensive free energy barrier. We discover that the
disordered symmetric phase of this system may be locally stable with respect to
the ordered phase at all inverse temperatures except for a unique eureka point
$\beta_b$ at which it is only marginally stable. The eureka point $\beta_b$
serves as a backdoor to access the hidden ground state with vanishing free
energy barrier. It exists in an infinite series of planted random graph
ensembles and we determine their structural parameters analytically. The
revealed new type of free energy landscape may also exist in other planted
random-graph optimization problems at the interface of statistical physics and
statistical inference.
