Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm

Abstract

We study minimum vertex cover problems on random α-uniform hypergraphs using two different approaches, a replica method in statistical mechanics of random systems and a leaf removal algorithm. It is found that there exists a phase transition at the critical average degree e/(α-1). Below the critical degree, a replica symmetric ansatz in the statistical-mechanical method holdsand the algorithm estimates a solution of the problem which coincide with that by the replica method. In contrast, above the critical degree, the replica symmetric solution becomes unstable and these methods fail to estimate the exact solution.These results strongly suggest a close relation between the replica symmetry and the performance of approximation algorithm.

5 pages, 2 figures

References in corpus (5)

• Message passing for vertex covers
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Phase transition for cutting-plane approach to vertex-cover problem
• 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

Cited by in corpus (10)

• Covering Problems and Core Percolations on Hypergraphs
• Statistical Mechanics of the Minimum Dominating Set Problem
• Kernel method for corrections to scaling
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• Typical Approximation Performance for Maximum Coverage Problem
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics
• Statistical mechanics of the minimum vertex cover problem in stochastic block models