Stable Set Problem: Branch & Cut Algorithms

Abstract

In this article, we provide an overview on how the maximum weighted stable set problem can be solved exactly with Branch & Cut techniques. In addition, we provide selected references to other exact methods. We start with a brief introduction of the stable set problem and a few basic definitions but assuming that the reader is already familiar with the basic concepts. The main stress of this article lies in the review of polyhedral results for the stable set polytope in section “Stable Set Polytope” and the discussion of separation procedures, section “Separation”. An efficient Branch & Cut algorithm needs, in addition to strong separation routines, also a good branching strategy. This is discussed in section “Branching”. At the end, some implementation aspects are considered.