The canonical facets of multi-separator polytopes
2026-08-17 • Discrete Mathematics
Discrete MathematicsMachine Learning
AI summaryⓘ
The authors explore a new way to look at a problem called the graph multi-separator problem, which is used in image segmentation to divide images into parts. They start by describing the problem using a mathematical model called an integer linear program and study the shape formed by all solutions (the multi-separator polytope). They identify key boundaries of this shape based on simple graph properties and then improve these descriptions for special cases, like paths. Lastly, they compare this problem’s shape to other known shapes in mathematics to understand their relationships better.
graph multi-separator probleminteger linear program (ILP)polytopefacetsimage segmentationtotally dual integralboolean quadric polytopelifted multicut problemodd-cycle inequalities
Authors
Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, Lucas Fabian Naumann, Shengxian Zhao
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, 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.