Generalizations of Cliques, Odd Cycles and Anticycles and Their Relation to Independence System Polyhedra
Reinhardt Euler, Michael Jünger, Gerhard Reinelt · Mathematics of Operations Research · 1987
Padberg (Padberg, M. W. 1973. On the facial structure of set packing polyhedra. Math. Programming 5 199–215.) has shown that if a graph G with vertex set V constitutes a clique (odd cycle, odd anticycle), then the inequality Σ x∈V x v ≤ 1 (Σ x∈V x v ≤ ½(|V| − 1), Σ x∈V x v ≤ 2) defines a facet of P(ℐ ST (G)), the convex hull of the incidence vectors of stable sets in G. We generalize the concepts of cliques, odd cycles and anticycles to arbitrary independence systems (E, ℐ) and show that the corresponding inequalities define facets of P(ℐ), the convex hull of the incidence vectors of independent sets.