A Lagrangian Relaxation for the Maximum Stable Set Problem

2009/03/08 by Manoel Campêlo, Campelo, Manoel, Ricardo C. Corrêa +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.0903.1407

openalex publication_date 2009/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a new integer programming formulation for the problem of finding a maximum stable set of a graph based on representatives of stable sets. In addition, we investigate exact solutions provided by a Lagrangian decomposition of this formulation in which only one constraint is relaxed. Some computational experiments were carried out with an effective multi-threaded implementation of our algorithm in a multi-core system, and their results are presented.

Related

• Application of the Lovász-Schrijver Lift-and-Project Operator to Compact Stable Set Integer Programs
• An \cal O(mlog n) algorithm for the weighted stable set problem in claw-free graphs with α(G) ≤ 3
• A hybrid constraint programming and semidefinite programming approach for the stable set problem
• The maximum weight stable set problem in (P₆,bull)-free graphs
• Maximum independent set (stable set) problem: Computational testing with binary search and convex programming using a bin packing approach