Clique-Web Facets for Multicut Polytopes

Abstract
Let G = (V, E) be a graph. An edge set {uv ∈ E|u ∈ Si, v ∈ Sj, i ≠ j}, where S1, …, Sk is a partition of V, is called a multicut with k shores. We investigate the polytopes MCk≤(n) and MCk≥(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 Kn. 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 MCk≤(n) and MCk≥(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.

This publication has 0 references indexed in Scilit: