Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions

Abstract

We consider the general problem of finding the minimum weight $\bm$-matching on arbitrary graphs. We prove that, whenever the linear programming (LP) relaxation of the problem has no fractional solutions, then the belief propagation (BP) algorithm converges to the correct solution. We also show that when the LP relaxation has a fractional solution then the BP algorithm can be used to solve the LP relaxation. Our proof is based on the notion of graph covers and extends the analysis of (Bayati-Shah-Sharma 2005 and Huang-Jebara 2007}. These results are notable in the following regards: (1) It is one of a very small number of proofs showing correctness of BP without any constraint on the graph structure. (2) Variants of the proof work for both synchronous and asynchronous BP; it is the first proof of convergence and correctness of an asynchronous BP algorithm for a combinatorial optimization problem.

28 pages, 2 figures. Submitted to SIAM journal on Discrete Mathematics on March 19, 2009; accepted for publication (in revised form) August 30, 2010; published electronically July 1, 2011

References in corpus (11)

• Phase Transitions in the Coloring of Random Graphs
• Consensus Propagation
• Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes
• The number of matchings in random graphs
• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• Convergence of the Min-Sum Algorithm for Convex Optimization
• MAP Estimation, Message Passing, and Perfect Graphs
• A rigorous proof of the cavity method for counting matchings
• Finding long cycles in graphs
• Sudden emergence of q-regular subgraphs in random graphs

Cited by in corpus (16)

• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• The Bethe Permanent of a Non-Negative Matrix
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• A rigorous analysis of the cavity equations for the minimum spanning tree
• Exactness of Belief Propagation for Some Graphical Models with Loops
• Recovery thresholds in the sparse planted matching problem
• The planted $k$-factor problem
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles
• Typical Performance of Approximation Algorithms for NP-hard Problems
• Minimum Weight Perfect Matching via Blossom Belief Propagation
• Hidden Hamiltonian Cycle Recovery via Linear Programming
• Max-Product Belief Propagation for Linear Programming: Applications to Combinatorial Optimization
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising
• Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
• Planted matching problems on random hypergraphs