# The canonical facets of multi-separator polytopes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 37 references that are in the map.
- First posted on arXiv 17 Aug 2026.

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

- [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)
- [A Polyhedral Study of Lifted Multicuts](https://mlsanity.com/paper/2202.08068/) (2022)
- [A Graph Multi-separator Problem for Image Segmentation](https://mlsanity.com/paper/2307.04592/) (2023)
- [Box Facets and Cut Facets of Lifted Multicut Polytopes](https://mlsanity.com/paper/2402.16814/) (2024)

## Abstract (arXiv)

We initiate a polyhedral study of the graph multi-separator problem proposed by Irmai et al. (2024) as an alternative to the lifted multicut problem for application to the task of image segmentation. Starting with an integer linear program (ILP) formulation and the multi-separator polytope spanned by its feasible solutions, we characterize in terms of efficiently-decidable, graph-theoretic conditions all facets induced by inequalities of the ILP. We proceed by strengthening these inequalities and describing additional facets of some multi-separator polytopes induced by the stronger inequalities. Specifically, we obtain a totally dual integral description of the multi-separator polytope for paths in the case where separation is considered for all vertex pairs. Finally, we relate the multi-separator polytope to the boolean quadric polytope, showing that facets induced by odd-cycle inequalities do not transfer generally, and to the lifted multicut polytope, showing that either polytope is a projection of a face of the other.