Box Facets and Cut Facets of Lifted Multicut Polytopes

The lifted multicut problem is a combinatorial optimization problem whose feasible solutions relate one-to-one to the decompositions of a graph G = (V, E). Given an augmentation widehatG = (V, E cup F) of G and given costs c ∈ ℝE cup F, the objective is to minimize the sum of those cuw with uw ∈ E cup F for which u and w are in distinct components. For F = emptyset, the problem specializes to the multicut problem, and for E = tbinomV2 to the clique partitioning problem. We study a binary linear program formulation of the lifted multicut problem. More specifically, we contribute to the analysis of the associated lifted multicut polytopes: Firstly, we establish a necessary, sufficient and efficiently decidable condition for a lower box inequality to define a facet. Secondly, we show that deciding whether a cut inequality of the binary linear program defines a facet is NP-hard.