Mézard Marc, Tarzia Marco
CNRS, Laboratoire de Physique Théorique et Modèles Statistiques, Université Paris-Sud, UMR 8626, Orsay Cedex 91405, France.
Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Oct;76(4 Pt 1):041124. doi: 10.1103/PhysRevE.76.041124. Epub 2007 Oct 18.
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.
在本文中，我们对击中集（HS）问题进行了详细研究。该问题是标准顶点覆盖问题对超图的一种推广：要寻找一种粒子配置，其密度最小，使得超图的每条超边至少包含一个粒子。它还可用于重要的实际任务，比如在分组测试程序中，通过混合测试在一大组物品中检测出有缺陷的物品。利用基于腔方法的统计力学方法，我们研究了随机正则超图情况下HS问题的相图。根据变量值和测试度的不同，会出现不同情况：HS问题可能处于复制对称相，也可能处于一步复制对称破缺相。在这两种情况下，我们给出了关于粒子最小密度和相空间结构的明确结果。因此，这些问题在某种意义上比原始的顶点覆盖问题更简单，在原始顶点覆盖问题中，由于需要完全的复制对称破缺，到目前为止还无法得出精确结果。最后，我们表明基于置信传播和调查传播算法的抽取程序为解决击中集问题的大型单个实例提供了非常有效的策略。
