Statistical Mechanics of the Hyper Vertex Cover Problem

Abstract

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.

Submitted to PRE

References in corpus (18)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Phase Transitions in the Coloring of Random Graphs
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Lattice Glass Models
• Coloring random graphs
• The Entropy of the K-Satisfiability Problem
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• Glass models on Bethe lattices
• A variational description of the ground state structure in random satisfiability problems
• Core percolation in random graphs: a critical phenomena analysis
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Message passing for vertex covers
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Glassy behavior induced by geometrical frustration in a hard-core lattice gas model

Cited by in corpus (15)

• Critical phenomena in complex networks
• Compressed Genotyping
• Statistical Mechanics of maximal independent sets
• The hard-core model on random graphs revisited
• Group testing with Random Pools: Phase Transitions and Optimal Strategy
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Ground-State Entropy of the Random Vertex-Cover Problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
• Typical behavior of the linear programming method for combinatorial optimization problems: From a statistical-mechanical perspective
• Statistical Physics of Group Testing
• Typical Approximation Performance for Maximum Coverage Problem
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Statistical mechanics of the minimum vertex cover problem in stochastic block models