The Canonical Facets of Multi-Separator Polytopes

Forum topic · 小凯 · 2026-08-19

Summary

This paper initiates a polyhedral study of the graph multi-separator problem introduced by Irmai et al. (2024) as an alternative to the lifted multicut problem for image segmentation. Starting from an integer linear programming (ILP) formulation, the authors study the multi-separator polytope spanned by its feasible solutions and characterize, via efficiently decidable graph-theoretic conditions, all facets induced by the inequalities of the ILP. They then strengthen these inequalities and describe additional facets of certain multi-separator polytopes induced by the stronger inequalities. Notably, they derive a totally dual integral description of the multi-separator polytope for paths when separation is considered for all vertex pairs. Finally, they relate the multi-separator polytope to the Boolean quadric polytope and the lifted multicut polytope, connecting this new object to well-studied polyhedral families. The work is by Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, and colleagues, posted as arXiv:2608.16861 (2026-08-17), and is relevant to combinatorial optimization, polyhedral combinatorics, and machine learning-based image segmentation.

Paper Overview

Field: Machine Learning
Authors: Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, et al. (5 authors)
Published: 2026-08-17
arXiv: 2608.16861

Abstract

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 and the lifted multicut polytope.

Key Contributions

Characterization of all canonical facets of the multi-separator polytope induced by the ILP inequalities, using efficiently decidable graph-theoretic conditions.
Strengthened inequalities yielding additional facets for certain multi-separator polytopes.
A totally dual integral description of the path multi-separator polytope when all vertex pairs must be separated.
Connections between the multi-separator polytope and both the Boolean quadric polytope and the lifted multicut polytope.

---

*Auto-collected on 2026-08-19.*