Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem

Pan Zhang, Ying Zeng, Haijun Zhou

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. I…