  The effects of constraint relaxation on dynamic critical phenomena in the
Minimum Vertex Cover (MVC) problem on Erd\H{o}s-R\'enyi 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.
