Statistical Mechanics of maximal independent sets
arXiv:0907.3309 · doi:10.1103/PhysRevE.80.061136
Abstract
The graph theoretic concept of maximal independent set arises in several practical problems in computer science as well as in game theory. A maximal independent set is defined by the set of occupied nodes that satisfy some packing and covering constraints. It is known that finding minimum and maximum-density maximal independent sets are hard optimization problems. In this paper, we use cavity method of statistical physics and Monte Carlo simulations to study the corresponding constraint satisfaction problem on random graphs. We obtain the entropy of maximal independent sets within the replica symmetric and one-step replica symmetry breaking frameworks, shedding light on the metric structure of the landscape of solutions and suggesting a class of possible algorithms. This is of particular relevance for the application to the study of strategic interactions in social and economic networks, where maximal independent sets correspond to pure Nash equilibria of a graphical game of public goods allocation.
References in corpus (27)
- The Bethe lattice spin glass revisited
- Glassy dynamics of kinetically constrained models
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- 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
- Lattice Glass Models
- Edwards measures for powders and glasses
- Reconstruction on trees and spin glass transition
- Boosting search by rare events
- Glassiness in a model without energy barriers
- Clusters of solutions and replica symmetry breaking in random k-satisfiability
- On the freezing of variables in random constraint satisfaction problems
- Statistical physics of the Schelling model of segregation
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Landscape of solutions in constraint satisfaction problems
- Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
- Vertex cover problem studied by cavity method: Analytics and population dynamics
- Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
- Geometrical organization of solutions to random linear Boolean equations
- Glassy behavior induced by geometrical frustration in a hard-core lattice gas model
- A Lattice Model for Colloidal Gels and Glasses
- Jamming, freezing and metastability in one-dimensional spin systems
- Statistical Mechanics of the Hyper Vertex Cover Problem
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Metastable states of the Ising chain with Kawasaki dynamics
- Metastable configurations of spin models on random graphs
- On the phase transitions of graph coloring and independent sets
Cited by in corpus (13)
- Statistical physics of hard combinatorial optimization: The vertex cover problem
- The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
- Statistical physics approach to graphical games: local and global interactions
- Fixation and escape times in stochastic game learning
- Generalized minimum dominating set and application in automatic text summarization
- Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
- Statics and dynamics of selfish interactions in distributed service systems
- Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
- Coordination problems on networks revisited: statics and dynamics
- Constructing Concrete Hard Instances of the Maximum Independent Set Problem
- Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
- Extended Yard Sale model of wealth distribution on Erdős-Rényi random networks
- Solving Graph-based Public Good Games with Tree Search and Imitation Learning