Clique-web facets for multicut polytopes

Let be a graph. An edge set , where is a partition of V, is called a multicut with k shores. The authors investigate the polytopes and that are defined as the convex hulls of the incidence vectors of all multicuts with at most k shores and at least k shores, respectively, of the complete graph . They introduce a large class of inequalities, called clique-web inequalities, valid for these polytopes, and provide a quite complete characterization of those clique-web inequalities that define facets of and . Using general facet manipulation techniques like collapsing and node splitting the authors construct further new classes of facets for these multicut polytopes. They also exhibit a class of clique-web facets for which the separation problem can be solved in polynomial time.