2007/07/03 by Marc Mézard, M. Mézard, Marco Tarzia +1 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Medicine · Physics and Astronomy · #Advanced biosensing and bioanalysis techniques #Computer science #Cover (algebra) #Covering problems #Discrete mathematics #Generalization #Graph #Hypergraph #Machine Learning and Algorithms #Mathematics #Physics #Quantum mechanics #Replica #SARS-CoV-2 detection and testing #Set (abstract data type) #Statistical mechanics #Statistical physics #Symmetry breaking #Vertex (graph theory) #Vertex cover #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physreve.76.041124
Submitted to PRE
arxiv created 2007/07/03 · openalex publication_date 2007/10/18 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
In this paper we present a detailed study of the hitting set (HS) problem. 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 HS problem, in the case of random regular hypergraphs. Depending on the values of the variables and tests degrees different situations can occur: The HS 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 hitting set problem.