Box Facets and Cut Facets of Lifted Multicut Polytopes
This work addresses combinatorial optimization in graph decomposition, providing theoretical insights into facet properties, but it is incremental as it builds on existing lifted multicut formulations.
The paper tackles the lifted multicut problem by analyzing its polytope facets, establishing an efficiently decidable condition for lower box inequalities to define facets and proving that deciding facet-defining cut inequalities is NP-hard.
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.