CLIQUE-WEB FACETS FOR MULTICUT POLYTOPES

Let G = (V, E) be a graph. An edge set {uv is-an-element-of E\u is-an-element-of S(i), v is-an-element-of S(j), i not-equal j}, where S1,..., S(k) is a partition of V, is called a multicut with k shores. We investigate the polytopes MC(k)less-than-or-equal-to (n) and MC(k)greater-than-or-equal-to (n) 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 K(n). We 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 MC(k)less-than-or-equal-to (n) and MC(k)greater-than-or-equal-to (n). Using general facet manipulation techniques like collapsing and node splitting we construct further new classes of facets for these multicut polytopes. We also exhibit a class of clique-web facets for which the separation problem can be solved in polynomial time.