The bottom line: a new paper works out exactly which mathematical inequalities are essential for solving the "multi-separator" problem, a graph-based model for splitting an image into distinct regions. That matters because knowing the essential inequalities — the facets of the underlying polytope — is what lets solvers like Gurobi or SCIP prune bad solutions fast instead of grinding through a combinatorial explosion of possibilities.
Image segmentation — deciding which pixels belong to which object or region — is often solved by turning the image into a graph, where nodes are pixels or superpixels and edges connect neighbors. One established approach, the lifted multicut problem, decides which edges to "cut" to separate regions. In 2024, Irmai et al. proposed an alternative called the multi-separator problem, which instead picks a small set of vertices whose removal disconnects the parts of the graph that are supposed to belong to different regions — closer to drawing a boundary line than snipping individual connections.
Any such combinatorial problem can be written as an integer linear program (ILP): a set of 0/1 decision variables (which vertices form the separator) subject to linear constraints, optimized to minimize a cost function. The feasible integer solutions define the vertices of a polytope, and in practice, the tighter and more accurate the linear description of that polytope, the faster a branch-and-cut solver converges to a provable optimum. Loose or redundant constraints, by contrast, waste computation on regions of the search space that could never contain an optimal integer solution.
The paper's central contribution is a full characterization of which inequalities in the original ILP formulation are actually facets of the multi-separator polytope — the strongest possible linear constraints, each corresponding to a genuine face of the solution shape. The authors show this can be checked using efficiently-decidable, purely graph-theoretic conditions, meaning a solver (or a human) can determine facet status by inspecting properties of the graph rather than solving another hard optimization problem.
Beyond confirming which of the original inequalities are facet-defining, the authors strengthen some of them and identify additional facets induced by these tightened versions. For paths specifically — the simplest connected graph structure — when separation is required between every pair of vertices, they obtain a totally dual integral (TDI) description of the polytope. A TDI system is a particularly strong structural guarantee: it means the linear relaxation's dual problem always has an integer optimal solution, which in turn certifies that the linear program's optimal value equals the integer program's optimal value for that case, closing the gap between the relaxed and true problem entirely.
The paper also places the multi-separator polytope in context by relating it to two well-known relatives: the boolean quadric polytope and the lifted multicut polytope. One finding is a cautionary one for anyone tempted to reuse known results: odd-cycle inequalities, a classic and powerful family of facets for the boolean quadric polytope (used, for instance, in max-cut and correlation clustering formulations), do not generally transfer as facets to the multi-separator setting. On the other hand, the authors show a cleaner structural link to the lifted multicut polytope: each of the two polytopes can be obtained as a projection of a face of the other, formally connecting the multi-separator and multicut approaches to segmentation at the polyhedral level.
For practitioners, none of this changes an image pipeline overnight, but it is exactly the kind of groundwork that eventually does. Facet characterizations turn into cutting-plane routines, and cutting-plane routines are what let exact or near-exact ILP solvers handle segmentation instances that would otherwise be intractable at scale. The TDI result for paths, in particular, gives a concrete benchmark case where the integer and continuous relaxations coincide — a useful sanity check and building block for anyone extending the model to more general graphs like grids or region-adjacency graphs used in real segmentation pipelines.
Sources: Irmai et al., "The graph multi-separator problem" (2024), as referenced in the source paper · arXiv:2608.16861v1, "The canonical facets of multi-separator polytopes", http://arxiv.org/abs/2608.16861v1
