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.
Introduction
The standard Vertex Cover problem involves finding the smallest set of vertices in a graph such that every edge is connected to at least one vertex in the set. This paper addresses the Hyper Vertex Cover (HVC) problem, also known as the Hitting Set (HS) problem, where edges are replaced by hyperedges containing $K$ variables. The goal is to find the minimum number of "active" variables such that every hyperedge is covered.
This problem has significant practical applications in Group Testing. For instance, in DNA screening or blood sample testing, one aims to identify a small number of defective items using a minimal number of pooled tests. Identifying these items is mathematically equivalent to solving the HVC problem. While the standard Vertex Cover ($K=2$) is notoriously difficult to solve exactly using physics-based methods, the hypergraph version ($K>2$) often proves more tractable.
Theoretical Framework: The Cavity Method
To analyze the HVC problem, we treat it as a physical system of particles and apply the Cavity Method, a technique from the statistical mechanics of disordered systems. This method allows us to model how local information, or "messages," propagates through the graph structure.
We employ two primary assumptions in our analysis:
- Replica Symmetric (RS) Ansatz: This assumes the system exists in a single equilibrium state.
- 1-step Replica Symmetry Breaking (1RSB): This more complex assumption is used when the solution space "shatters" into many disconnected clusters, a phenomenon common in hard optimization problems.
Phase Transitions and the Entropy Crisis
A critical finding of this study is the identification of an "entropy crisis." As the constraints on the system increase, the simple RS solution eventually fails because it predicts a negative entropy—mathematically implying there are fewer than zero ways to solve the problem. This transition marks the point where the solution space clusters, making the problem significantly harder for local search algorithms.
In the 1RSB phase, solutions clump into clusters. Moving between these clusters requires changing many variables simultaneously, which explains why traditional algorithms often fail. However, Survey Propagation (SP) is specifically designed to model the distribution of these clusters, allowing it to navigate this complex landscape.
Key Results and Algorithmic Performance
Our analysis of random regular hypergraphs—where every variable is connected to $L$ tests and every test involves $K$ variables—yields several key insights:
- Tractability: For $K > 2$, the problem often falls into the 1RSB category, allowing for explicit, exact results for the minimal density of active particles ($\rho_{cov}$) that have remained elusive in the $K=2$ case.
- Numerical Success: In tests on large-scale instances ($N \approx 12,000$), the Survey Propagation algorithm significantly outperformed standard greedy heuristics. SP achieved a density of $\rho \approx 0.182$, remarkably close to the theoretical limit of $\rho_{cov} \approx 0.178$, whereas the greedy approach only reached $\rho \approx 0.212$.
Conclusion and Future Work
While this work provides a comprehensive map of the phase diagram for random regular hypergraphs, challenges remain. For certain parameters, even the 1RSB approach becomes unstable, requiring higher-order symmetry breaking. Furthermore, real-world applications often involve non-regular topologies (e.g., scale-free networks). Extending these statistical mechanics tools to such architectures is a vital next step for improving group testing and network analysis procedures.
Summary updated