Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem

Abstract

The effects of constraint relaxation on dynamic critical phenomena in the Minimum Vertex Cover (MVC) problem on Erdős-Rényi random graphs are investigated using Markov chain Monte Carlo simulations. Following our previous work that revealed the reduction of the critical temperature by constraint relaxation based on the penalty function method, this study focuses on investigating the critical properties of the relaxation time along its phase boundary. It is found that the dynamical correlation function of MVC with respect to the problem size and the constraint strength follows a universal scaling function. The analysis shows that the relaxation time decreases as the constraints are relaxed. This decrease is more pronounced for the critical amplitude than for the critical exponent, and this result is interpreted in terms of the system's microscopic energy barriers due to the constraint relaxation.

7 pages, 8 figures. arXiv:2311.13237

References in corpus (9)

• Ising formulations of many NP problems
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Parallel Tempering: Theory, Applications, and New Perspectives
• Make life simple: unleash the full power of the parallel tempering algorithm
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs