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 (2)

• Immunization of Real Complex Communication Networks
• Distance-d covering problems in scale-free networks with degree correlations

Cited by in corpus (8)

• Critical phenomena in complex networks
• Statistical Mechanics of the Hyper Vertex Cover Problem
• 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
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Statistical Physics of Group Testing