Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs

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.

arXiv comment20 pages, 15 figures

References in corpus (17)

• Ising formulations of many NP problems
• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Quantum Annealing in the Transverse Ising Model
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• The Bethe lattice spin glass revisited
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• The number of matchings in random graphs
• A variational description of the ground state structure in random satisfiability problems
• Core percolation in random graphs: a critical phenomena analysis
• 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
• Kernel method for corrections to scaling
• Statistical Mechanics of maximal independent sets
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Continuous phase transition in a spin-glass model without time-reversal symmetry
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem

Cited by in corpus (1)

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