Message passing for vertex covers

Abstract

Constructing a minimal vertex cover of a graph can be seen as a prototype for a combinatorial optimization problem under hard constraints. In this paper, we develop and analyze message passing techniques, namely warning and survey propagation, which serve as efficient heuristic algorithms for solving these computational hard problems. We show also, how previously obtained results on the typical-case behavior of vertex covers of random graphs can be recovered starting from the message passing equations, and how they can be extended.

25 pages, 9 figures - version accepted for publication in PRE

References in corpus (18)

• The Bethe lattice spin glass revisited
• The structural glass transition and the entropy of the metastable states
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Lattice Glass Models
• Glass models on Bethe lattices
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Core percolation in random graphs: a critical phenomena analysis
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Immunization of Real Complex Communication Networks
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Vertex cover problem studied by cavity method: Analytics and population dynamics
• Computational complexity arising from degree correlations in networks
• Distance-d covering problems in scale-free networks with degree correlations
• 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
• An algorithm for counting circuits: application to real-world and random graphs
• Dynamics of heuristic optimization algorithms on random graphs

Cited by in corpus (30)

• Critical phenomena in complex networks
• The theory of percolation on hypergraphs
• The hard-core model on random graphs revisited
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• The nature of hypergraph $k$-core percolation problems
• Dynamical replica analysis of processes on finitely connected random graphs I: vertex covering
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• 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
• Determining the Solution Space of Vertex-Cover by Interactions and Backbones
• The statistical mechanics of random set packing and a generalization of the Karp-Sipser algorithm
• Two faces of greedy leaf removal procedure on graphs
• Spin-glass model for the C-dismantling problem
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Statistical Physics of Group Testing
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• A residual-based message passing algorithm for constraint satisfaction problems
• 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
• Research on Solution Space of Bipartite Graph Vertex-Cover by Maximum Matchings
• The network source location problem: ground state energy, entropy and effects of freezing
• Organization mechanism and counting algorithm on Vertex-Cover solutions
• Witness of unsatisfiability for a random 3-satisfiability formula
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Statistical mechanics of the minimum vertex cover problem in stochastic block models
• Low Auto-correlation Binary Sequences explored using Warning Propagation
• Fast convergence to an approximate solution by message-passing for complex optimizations