Polyhedral Properties of Clutter Amalgam

A clutter L is a collection of subsets of a ground set E(L) with the property that, for every pair A(i), A(j) is-an-element-of L, A(i) is neither contained in nor contains A(j). A cover of L is a subset of E intersecting every member of L. The covering polytope Q(L), associated with a clutter L, is the convex hull of the incidence vectors of the covers of L. The polytope Q(L) provides a common generalization for several polytopes associated with combinatorial optimization problems (stable set, knapsack, acyclic subdigraph, bipartite subgraph, etc.) that can be formulated as covering problems with respect to suitably defined clutters. In this paper, a binary composition operation is described, the clutter amalgam, that combines two clutters L1 and L2 to produce a new clutter L called amalgam of L1 and L2. Furthermore, an isomorphic polyhedral composition operation is introduced that combines the linear descriptions of the polytopes Q(L1) and Q(L2) and produces a linear description of the polytope Q(L). The clutter amalgam operation has the crucial property that if the clutters L1 and L2 are ideal then the amalgam L is also ideal. Finally, the restriction of the clutter amalgam to graphs properly generalizes the graph amalgam introduced by Burlet and Fonlupt and defines a new perfection-preserving operation.