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' - the set (x)), for any vertex x of G'. A necessary and sufficient condition is given for the graphs obtained by Chvatal's substitution procedure to be facet producing.