Clique-Web Facets for Multicut Polytopes

Let G = (V, E) be a graph. An edge set {uv ∈ E|u ∈ S_i, v ∈ S_j, i ≠ j}, where S₁, …, S_k is a partition of V, is called a multicut with k shores. We investigate the polytopes MC_k^≤(n) and MC_k^≥(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^≤(n) and MC_k^≥(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.