Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem.
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; (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, and (3) the dynamical transition temperature T(d) and Kauzmann temperature T(K) is equal to each other. Similar results are obtained on random Poissonian graphs.
Key Laboratory of Frontiers in Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Beijing 100190, China.
Pan
P
Zhang
Ying
Y
Zeng
Haijun
H
Zhou