  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.
