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

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.