Statistical mechanics of the hitting set problem
- 18 October 2007
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review E
- Vol. 76 (4), 041124
- https://doi.org/10.1103/physreve.76.041124
Abstract
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.Keywords
Other Versions
This publication has 29 references indexed in Scilit:
- Message passing for vertex coversPhysical Review E, 2006
- Long-Range Frustration in a Spin-Glass Model of the Vertex-Cover ProblemPhysical Review Letters, 2005
- Vertex cover problem studied by cavity method: Analytics and population dynamicsZeitschrift für Physik B Condensed Matter, 2003
- The Cavity Method at Zero TemperatureJournal of Statistical Physics, 2003
- Core percolation in random graphs: a critical phenomena analysisZeitschrift für Physik B Condensed Matter, 2001
- Minimal vertex covers on finite-connectivity random graphs: A hard-sphere lattice-gas picturePhysical Review E, 2001
- The Bethe lattice spin glass revisitedZeitschrift für Physik B Condensed Matter, 2001
- Number of Guards Needed by a Museum: A Phase Transition in Vertex Covering of Random GraphsPhysical Review Letters, 2000
- On the independence number of random graphsDiscrete Mathematics, 1990
- Independent sets in random sparse graphsNetworks, 1984