Issue |
EPL
Volume 147, Number 1, July 2024
|
|
---|---|---|
Article Number | 11005 | |
Number of page(s) | 7 | |
Section | Statistical physics and networks | |
DOI | https://doi.org/10.1209/0295-5075/ad5102 | |
Published online | 25 July 2024 |
Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem
1 Graduate School of Arts and Sciences, The University of Tokyo - Komaba, Meguro-ku, Tokyo 153-8902, Japan
2 Komaba Institute for Science The University of Tokyo - 3-8-1 Komaba, Meguro-ku, Tokyo 153-8902, Japan
3 Fujitsu Limited - 4-1-1 Kamikodanaka, Nakahara-ku, Kawasaki, 211-8588, Japan
Received: 3 April 2024
Accepted: 28 May 2024
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.
© 2024 EPLA
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.