Graph substitution and set packing polytopes

Facets of the set packing polytope provide strong cutting planes for set packing and partitioning problems. Set packing polytopes are in a one‐to‐one correspondence with graphs. The facets of P(G), the set packing polytope associated with the graph G, are related to certain subgraphs of G. Of particular interest are those subgraphs G′ which are facet producing, i.e., which give rise to facets of P(G′) that cannot be obtained by lifting a facet of P(G′ ‐ {x}), for any vertex x of G′. In this paper we characterize the facets of the set packing polytopes associated with the class of graphs obtained by Chvátal's substitution procedure, and give necessary and sufficient conditions for these graphs to be facet‐producing.