Statistical Mechanics of the Hyper Vertex Cover Problem

Understand

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.