  The vertex-cover problem is a prototypical hard combinatorial optimization
problem. It was studied in recent years by physicists using the cavity method
of statistical mechanics. In this paper, the stability of the
finite-temperature replica-symmetric (RS) and the first-step
replica-symmetry-broken (1RSB) cavity solutions of the vertex cover problem on
random regular graphs of finite vertex-degree $K$ are analyzed by population
dynamics simulations. We found that (1) the lowest temperature for the RS
solution to be stable, $T_{RS}(K)$, is not a monotonic function of $K$, and (2)
at relatively large connectivity $K$ and temperature $T$ slightly below the
dynamic transition temperature $T_d(K)$, the 1RSB solutions with small but
non-negative complexity values are stable. Similar results are obtained on
random Poissonian graphs.
