Related Experiment Video
Updated: Jun 26, 2025

Setting Limits on Supersymmetry Using Simplified Models
Published on: November 15, 2013
Effect of constraint relaxation on the minimum vertex cover problem in random graphs
Aki Dote1,2, Koji Hukushima1,3
1Graduate School of Arts and Sciences, The University of Tokyo, Komaba, Meguro-ku, Tokyo 153-8902, Japan.
Abstract:
A statistical-mechanical study of the effect of constraint relaxation on the minimum vertex cover problem in Erdős-Rényi random graphs is presented. Using a penalty-method formulation for constraint relaxation, typical properties of solutions, including infeasible solutions that violate the constraints, are analyzed by means of the replica method and cavity method. The problem involves a competition between reducing the number of vertices to be covered and satisfying the edge constraints. The analysis under the replica-symmetric (RS) ansatz clarifies that the competition leads to degeneracies in the vertex and edge states, which determine the quantitative properties of the system, such as the cover and penalty ratios. A precise analysis of these effects improves the accuracy of RS approximation for the minimum cover ratio in the replica symmetry-breaking (RSB) region. Furthermore, the analysis based on the RS cavity method indicates that the RS/RSB boundary of the ground states with respect to the mean degree of the graphs is expanded, and the critical temperature is lowered by constraint relaxation.
Related Concept Videos
Constraints and Statical Determinacy
Stability of Equilibrium Configuration: Problem Solving
Problem-solving in the context of the stability of equilibrium configuration...
Stability of Equilibrium Configuration
A stable equilibrium occurs when a system tends to return to its original position when given a small displacement, and the potential energy is at its minimum. An example of a stable equilibrium is when a cantilever beam is fixed at one end and a weight is attached to the other end. If the weight...
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Routh-Hurwitz Criterion II
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...

