Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2009-07-19
Phys. Rev. E 80, 061136 (2009)
Physics
Condensed Matter
Disordered Systems and Neural Networks
Scientific paper
10.1103/PhysRevE.80.061136
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.
Dall'Asta Luca
Pin Paolo
Ramezanpour Abolfazl
No associations
LandOfFree
Statistical Mechanics of maximal independent sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Statistical Mechanics of maximal independent sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Mechanics of maximal independent sets will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-585991