A Branch and Bound Algorithm for the Stability Number of a Sparse Graph

We present a branch and bound algorithm for finding a maximum stable set in a graph. The algorithm uses properties of the stable set polytope to construct strong upper bounds. Specifically, it uses cliques, odd cycles, and a maximum matching on the remaining nodes. The cliques are generated via standard coloring heuristics, and the odd cycles are generated from blossoms found by a matching algorithm. We report computational experience on two classes of randomly generated graphs and on the DIMACS Challenge Benchmark graphs. These experiments indicate that the algorithm is quite effective, particularly for sparse graphs.