title: 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.
authors.affiliation: Institute for Scientific Interchange, Viale Settimio Severo 65, I-10133 Torino, Italy.
authors.forename: Martin
authors.initials: M
authors.lastname: Weigt
authors.forename: Haijun
authors.initials: H
authors.lastname: Zhou