Max-product belief propagation (BP) is a popular message-passing algorithm for computing a maximum-a-posteriori assignment in a graphical model. It has been shown that BP can solve a few classes of Linear Programming (LP) formulations to combinatorial optimization problems including maximum weight matching and shortest path. However, those LPs and corresponding BP analysis are very sensitive to underlying problem setups, and it has been not clear what extent these results can be generalized to. In this talk, I first present a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, network flow, traveling salesman, cycle packing and vertex cover. Using the criteria, we also construct the exact distributed algorithm, called Blossom-BP, solving the maximum weight matching problem over arbitrary graphs. It requires O(n^2) BP runs until it outputs the optimal solution, where n is the number of vertices of the graph. In essence, Blossom-BP offers a distributed version of the celebrated Blossom algorithm (Edmonds '1965) jumping at once over many sub-steps of the Blossom-V (most recent implementation of the Blossom algorithm due to Kolmogorov, 2011). Finally, I report the empirical performance of BP for solving large-scale combinatorial optimization problems, in particular focusing on maximum weight matching and traveling salesman problems. This talk is based on joint works with Sungsoo Ahn (KAIST), Michael Chertkov (LANL), Inho Cho (KAIST), Sejun Park (KAIST), and Dongsu Han (KAIST).