2014/01/30 by Marc Lelarge, Lelarge, Marc
Computer Science · Mathematics · Physics and Astronomy · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Mathematical Physics (math-ph) #Probability (math.PR) #cs.DM #cs.DS #cs.IT #math-ph #math.IT #math.MP #math.PR
paper · pdf · doi:10.48550/arxiv.1401.7923
revised version, 23 pages
openalex publication_date 2014/01/30 · arxiv created 2014/07/07 · arxiv updated 2014/07/09 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
For the minimum cardinality vertex cover and maximum cardinality matching problems, the max-product form of belief propagation (BP) is known to perform poorly on general graphs. In this paper, we present an iterative loopy annealing BP (LABP) algorithm which is shown to converge and to solve a Linear Programming relaxation of the vertex cover or matching problem on general graphs. LABP finds (asymptotically) a minimum half-integral vertex cover (hence provides a 2-approximation) and a maximum fractional matching on any graph. We also show that LABP finds (asymptotically) a minimum size vertex cover for any bipartite graph and as a consequence compute the matching number of the graph. Our proof relies on some subtle monotonicity arguments for the local iteration. We also show that the Bethe free entropy is concave and that LABP maximizes it. Using loop calculus, we also give an exact (also intractable for general graphs) expression of the partition function for matching in term of the LABP messages which can be used to improve mean-field approximations.