Reductions for the Stable Set Problem - Sewell, E. C.; Jacobson, S. H.; Kaul, Hemanshu (Algorithmic Operations Research, 2011)
One approach to finding a maximum stable set (MSS) in a graph is to try to reduce the size of the problem by transforming the problem into an equivalent problem on a smaller graph. This paper introduces several new reductions for the MSS problem, extends several well-known reductions to the maximum weight stable set (MWSS) problem, demonstrates how reductions for the generalized stable set problem can be used in conjunction with probing to produce powerful new reductions for both the MSS and MWSS problems, and shows how hypergraphs can be used to expand the capabilities of clique projections. The effectiveness of these new reduction techniques are illustrated on the DIMACS benchmark graphs, planar graphs, and a set of challenging MSS problems arising from Steiner Triple Systems.