Statistical Mechanics of the Hyper Vertex Cover Problem

Details Statistical Mechanics of the Hyper Vertex Cover Problem Statistical Mechanics of the Hyper Vertex Cover Problem

2007-07-02

arxiv.org/abs/0707.0189v2

Physics

Condensed Matter

Statistical Mechanics

Submitted to PRE

Scientific paper

10.1103/PhysRevE.76.041124

We introduce and study a new optimization problem called Hyper Vertex Cover. This problem is a generalization of the standard vertex cover to hypergraphs: one seeks a configuration of particles with minimal density such that every hyperedge of the hypergraph contains at least one particle. It can also be used in important practical tasks, such as the Group Testing procedures where one wants to detect defective items in a large group by pool testing. Using a Statistical Mechanics approach based on the cavity method, we study the phase diagram of the HVC problem, in the case of random regualr hypergraphs. Depending on the values of the variables and tests degrees different situations can occur: The HVC problem can be either in a replica symmetric phase, or in a one-step replica symmetry breaking one. In these two cases, we give explicit results on the minimal density of particles, and the structure of the phase space. These problems are thus in some sense simpler than the original vertex cover problem, where the need for a full replica symmetry breaking has prevented the derivation of exact results so far. Finally, we show that decimation procedures based on the belief propagation and the survey propagation algorithms provide very efficient strategies to solve large individual instances of the hyper vertex cover problem.

Affiliated with

Also associated with

No associations

Rating

Statistical Mechanics of the Hyper Vertex Cover Problem 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 the Hyper Vertex Cover Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical Mechanics of the Hyper Vertex Cover Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-692659