Belief propagation for the maximum-weight independent set and minimum spanning tree problems

The belief propagation (BP) algorithm is a message-passing algorithm that is used for solving probabilistic inference problems. In practice, the BP algorithm performs well as a heuristic in many application fields. However, the theoretical understanding of BP is limited. To improve the theoretical understanding of BP, the BP algorithm has been applied to many well-understood combinatorial optimization problems. In this paper, we consider BP applied to the maximum-weight independent set (MWIS) and minimum spanning tree (MST) problems.

Sanghavi et al. (2009) [12] applied the BP algorithm to the MWIS problem. We denote their algorithm by BP-MWIS. They showed that if the LP relaxation of the MWIS problem has a unique integral optimal solution and BP-MWIS converges, then BP-MWIS finds the optimal solution. Also, they showed that if the LP relaxation has a non-integral optimal solution, then BP-MWIS does not converge. In this paper, we precisely characterize the graphs for which BP-MWIS is guaranteed to find the optimal solution, regardless of the node weights.

Bayati et al. (2008) [2] applied the BP algorithm to the MST problem. We denote their algorithm by BP-MST. They showed that if BP-MST converges, then it finds the optimal solution. In this paper, however, we provide an instance for which BP-MST does not converge. Also, since this instance is small and simple, we believe that BP-MST does not converge for most instances encountered in practice.