Clustering analysis of the ground-state structure of the vertex-cover problem

Abstract

Vertex cover is one of the classical NP-complete problems in theoretical computer science. A vertex cover of a graph is a subset of vertices such that for each edge at least one of the two endpoints is contained in the subset. When studied on Erdos-Renyi random graphs (with connectivity c) one observes a threshold behavior: In the thermodynamic limit the size of the minimal vertex cover is independent of the specific graph. Recent analytical studies show that on the phase boundary, for small connectivities c<e, the system is replica symmetric, while for larger connectivities replica symmetry breaking occurs. This change coincides with a change of the typical running time of algorithms from polynomial to exponential. To understand the reasons for this behavior and to compare with the analytical results, we numerically analyze the structure of the solution landscape. For this purpose, we have also developed an algorithm, which allows the calculation of the backbone, without the need to enumerate all solutions. We study exact solutions found with a Branch-and-Bound algorithm as well as configurations obtained via a Monte Carlo simulation. We analyze the cluster structure of the solution landscape by direct clustering of the states, by analyzing the eigenvalue spectrum of correlation matrices and by using a hierarchical clustering method. All results are compatible with a change at c=e. For small connectivities, the solutions are collected in a finite small number of clusters, while the number of cluster diverges slowly with system size for larger connectivities and replica symmetry breaking, but not 1-RSB, occurs.

arXiv comment12 pages, 10 figures

References in corpus (24)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Simulated Tempering: A New Monte Carlo Scheme
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• 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
• Phase Transition in the Number Partitioning Problem
• Coloring random graphs
• The Entropy of the K-Satisfiability Problem
• Nature of the Spin Glass State
• Spin and link overlaps in 3-dimensional spin glasses
• A variational description of the ground state structure in random satisfiability problems
• Core percolation in random graphs: a critical phenomena analysis
• Random Costs in Combinatorial Optimization
• 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
• Ground-state clusters of two-, three- and four-dimensional +-J Ising spin glasses
• Statistical mechanics of the vertex-cover problem
• Spin Domains Generate Hierarchical Ground State Structure in J=+/-1 Spin Glasses
• Exactly solvable model with two conductor-insulator transitions driven by impurities
• Lack of Ultrametricity in the Low-Temperature phase of 3D Ising Spin Glasses
• A new method for analyzing ground-state landscapes: ballistic search
• The nature of ergodicity breaking in Ising spin glasses as revealed by correlation function spectral properties
• Extensive eigenvalues in spin-spin correlations: a tool for counting pure states in Ising spin glasses
• On the Tail of the Overlap Probability Distribution in the Sherrington--Kirkpatrick Model

Cited by in corpus (24)

• Critical phenomena in complex networks
• Survey Propagation as local equilibrium equations
• Core percolation on complex networks
• Efficient Algorithms for Searching the Minimum Information Partition in Integrated Information Theory
• Universality-class dependence of energy distributions in spin glasses
• Statistical Mechanics of maximal independent sets
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Numerical Solution-Space Analysis of Satisfiability Problems
• Phase transition for cutting-plane approach to vertex-cover problem
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• Solution-space structure of (some) optimization problems
• Replica symmetry breaking for Ulam's problem
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• Replica-symmetry breaking for directed polymers
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Optimal Vertex Cover for the Small-World Hanoi Networks
• Effect of constraint relaxation on dynamic critical phenomena in minimum vertex cover problem
• Phase transition for parameter learning of Hidden Markov Models
• Phase transition in the bipartite z-matching