The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm

Abstract

We analyse the asymptotic behaviour of random instances of the Maximum Set Packing (MSP) optimization problem, also known as Maximum Matching or Maximum Strong Independent Set on Hypergraphs. We give an analytical prediction of the MSPs size using the 1RSB cavity method from statistical mechanics of disordered systems. We also propose a heuristic algorithm, a generalization of the celebrated Karp-Sipser one, which allows us to rigorously prove that the replica symmetric cavity method prediction is exact for certain problem ensembles and breaks down when a core survives the leaf removal process. The $e$-phenomena threshold discovered by Karp and Sipser, marking the onset of core emergence and of replica symmetry breaking, is elegantly generalized to $c_s=\frac{e}{d-1}$ for one of the ensembles considered, where $d$ is the size of the sets.

References in corpus (4)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• On the freezing of variables in random constraint satisfaction problems
• Message passing for vertex covers
• Statistical Mechanics of the Hyper Vertex Cover Problem

Cited by in corpus (9)

• Network Controllability Is Determined by the Density of Low In-Degree and Out-Degree Nodes
• Statistical Mechanics of the Minimum Dominating Set Problem
• Controllability and maximum matchings of complex networks
• Minimum vertex cover problems on random hypergraphs: replica symmetric solution and a leaf removal algorithm
• Two faces of greedy leaf removal procedure on graphs
• Typical Approximation Performance for Maximum Coverage Problem
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Statistical-mechanical Analysis of Linear Programming Relaxation for Combinatorial Optimization Problems
• A local algorithm and its percolation analysis of bipartite $z$-matching problem