Box Facets and Cut Facets of Lifted Multicut Polytopes
<|reference_start|>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 $\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.<|reference_end|>
@article{naumann2024box,
    title={Box Facets and Cut Facets of Lifted Multicut Polytopes},
    author={Lucas Fabian Naumann, Jannik Irmai, Shengxian Zhao, Bjoern Andres},
    journal={arXiv preprint arXiv:2402.16814},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.16814},
    primaryClass={cs.DM cs.LG}
}