A Combined Parallel Lagrangian Decomposition and Cutting-Plane Generation for Maximum Stable Set Problems

We propose an integer programming formulation for the problem of finding the maximum k-partite induced sub-graph of a graph G based on representatives of stable sets. We investigate upper bounds provided by the solution, via a parallel sub-gradient algorithm, of a Lagrangian decomposition that breaks up this formulation into maximum weighted stable set problems for sub-graphs of G. Some computational experiments were carried out with an effective multi-threaded parallel implementation in a multi-core system, and their results are presented.