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. We call a cutset critical if its removal produces a graph whose independence number is greater than that of G. We use the concept of a critical cutset 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.
No takes yet. Share an insight, caveat, or question.
Balas et al. (1977) studied this question.