Vertices Belonging to All or to No Maximum Stable Sets of a Graph

The focus of the present paper is on the relations between the set D of optimal solutions of a maximum weighted stable set problem, and the set C of optimal solutions of its continuous relaxation. The main result is that if a variable takes a constant binary value in allX ∈ C, then it takes the same value in allX ∈ D (this may be contrasted with a well-known result of Nemhauser and Trotter, stating that if a variable takes a binary value in someX ∈ C, then it takes the same value in someX ∈ D). For any graph G, the set P of the vertices j such that Xⱼ has a constant binary value in allX ∈ C, can be efficiently detected; moreover, the results in this paper imply that in the unweighted case, the subgraph induced by P has the "strong" König–Egerváry property and that the subgraph induced by the complement of P has a perfect 2-matching: actually, the maximum stable sets of G are in a 1-to-1 correspondence with those of the latter subgraph.