Box Facets and Cut Facets of Lifted Multicut Polytopes

Abstract

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 G = (V, E F) of G and given costs c R^E F, the objective is to minimize the sum of those c_uw with uw E F for which u and w are in distinct components. For F = , the problem specializes to the multicut problem, and for E = V2 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.

Tasks

Reproductions