MAXIMUM WEIGHT PARTIAL COLORINGS ON SPARSE RANDOM GRAPHS

We examine the asymptotic behavior of optimal values and optimal configurations for the maximum weight partial coloring (MWPC) problem on sparse random graphs. The MWPC problem is a weighted version of the partial coloring problem, and it is a generalization of the maximum weight independent set (MWIS) problem. The MWPC problem is an illustrative example of how to employ the local weak convergence method on combinatorial optimization problems that are defined via a graphical model and have a nonbinary alphabet. Many of the results are inspired by Gamarnik, Nowicki, and Swirscsz [Random Structures Algorithms, 28 (2005), pp. 76-106]. They showed that if vertex weights were sampled independently from a nonatomic distribution and if a particular fixed point equation had a unique solution, then the scaled MWIS value on sparse Erdos-Renyi graphs converges in probability. Under the same conditions, Sanghavi and Shah [http://arxiv.org/pdf/cs/0508097v2(12 April 2008)] showed how the max-product message passing algorithm can be used to produce 1 + epsilon approximations with probability 1 - epsilon. There are major difficulties in applying the above techniques to other natural combinatorial optimization problems. We show how to strengthen them so that they can be applied to a new range of problems which includes the MWPC problem. In the MWPC case, we show how our techniques can be used to get new convergence results on sparse Erdos-Renyi graphs-even in the case where the weights are sampled from a discrete distribution. This depends on new results on how certain long range independence properties occur almost surely for branching processes.