Towards Understanding the Min-Sum Message Passing Algorithm for the Minimum Weighted Vertex Cover Problem: An Analytical Approach

Given a vertex-weighted undirected graph \(G=\langle V,E,w\rangle\), the minimum weighted vertex cover (MWVC) problem is to find a subset of vertices with minimum total weight such that every edge in the graph has at least one of its endpoints in it. The MWVC problem and its amenability to the min-sum message passing (MSMP) algorithm remain understudied despite the common occurrence of the MWVC problem and the common use of the MSMP algorithm in many areas of AI. In this paper, we first develop the MSMP algorithm for the MWVC problem that can be viewed as a generalization of the warning propagation algorithm. We then study properties of the MSMP algorithm for the MWVC problem on a special class of graphs, namely single loops. We compare our analytical results with experimental observations and argue that: (a) Our analytical framework is powerful in accurately predicting the behavior of the MSMP algorithm on the MWVC problem, and (b) for a given combinatorial optimization problem, it may be more effective to apply the MSMP algorithm on the MWVC problem that is equivalent to the given problem, instead of applying the MSMP algorithm on the given problem directly.