# Box Facets and Cut Facets of Lifted Multicut Polytopes

arXiv: https://arxiv.org/abs/2402.16814 · HTML: https://mlsanity.com/paper/2402.16814/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 23 references that are in the map.
- First posted on arXiv 26 Feb 2024.

## Builds on (most cited first, 5 of 5)

- [LMGP: Lifted Multicut Meets Geometry Projections for Multi-Camera Multi-Object Tracking](https://mlsanity.com/paper/2111.11892/) (2021)
- [Efficient Decomposition of Image and Mesh Graphs by Lifted Multicuts](https://mlsanity.com/paper/1505.06973/) (2015)
- [Higher-Order Minimum Cost Lifted Multicuts for Motion Segmentation](https://mlsanity.com/paper/1704.01811/) (2017)
- [Joint Graph Decomposition and Node Labeling: Problem, Algorithms, Applications](https://mlsanity.com/paper/1611.04399/) (2016)
- [A Polyhedral Study of Lifted Multicuts](https://mlsanity.com/paper/2202.08068/) (2022)

## Built on by (most cited first, 1 of 1)

- [The canonical facets of multi-separator polytopes](https://mlsanity.com/paper/2608.16861/) (2026)

## Abstract (arXiv)

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.