搞图分割优化的话，这篇把多分隔符问题的多面体结构讲清楚了，还给了路径情况的完整刻画，值得翻翻。
这篇论文对Irmai等人（2024）提出的图多分隔符问题展开多面体研究，该问题用于图像分割，是提升多割问题的替代方案。作者从整数线性规划（ILP）公式出发，用可高效判定的图论条件刻画了ILP不等式诱导的所有面。他们进一步强化不等式，描述了若干多分隔符多面体的额外面。对于路径图且考虑所有顶点对分离的情况，得到了全对偶整数（TDI）描述。论文还证明奇数环不等式诱导的面不会从多分隔符多面体迁移到布尔二次多面体，并揭示了多分隔符多面体与提升多割多面体互为某面的投影关系。
The canonical facets of multi-separator polytopes
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.