Critical Cutsets of Graphs and Canonical Facets of Set Packing Polytopes.

摘要

A cutset in a graph G with node set N is the set of edges joining the nodes in a subset of N to those not in the subset. A cutset is called critical if its removal produces a graph whose independence number is greater than that of G. The concept of a critical cutset is used to give first a necessary, then a sufficient condition for an inequality with 0-1 coefficients to be a facet of the set packing polytope defined by G.