  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 $\widehat{G} = (V, E \cup F)$ of $G$ and given costs
$c \in \mathbb{R}^{E \cup F}$, the objective is to minimize the sum of those
$c_{uw}$ with $uw \in 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 = \tbinom{V}{2}$ 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.
