The canonical facets of multi-separator polytopes

Bjoern Andres; Silvia Di Gregorio; Jannik Irmai; Lucas Fabian Naumann; Shengxian Zhao

cs.DMAug 17, 2026

The canonical facets of multi-separator polytopes

Authors: Bjoern Andres, Silvia Di Gregorio, Jannik Irmai, Lucas Fabian Naumann, Shengxian Zhao

Organizations: Faculty of Computer Science, TU Dresden, Germany · Center for Scalable Data Analytics and AI (ScaDS.AI) Dresden/Leipzig, Germany · Universit´e Sorbonne Paris Nord, CNRS, Laboratoire d’Informatique de Paris Nord, LIPN, F-93430 Villetaneuse, France

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.

Figures & tables

Panel of Figure 1 — Figure 1: Depicted above are a graph $G$ (solid black lines) and a set $F$ of vertex pairs called interactions (dashed green lines) that includes the edges $\{s_{1},w_{1}\}$ , $\{s_{2},s_{3}\}$ , $\{w_{2},w_{3}\}$ and the non-edges $\{u_{1},u_{3}\}$ , $\{u_{2},s_{2}\}$ , $\{s_{1},s_{2}\}$ , $\{u_{3},v_{3}\}$ , $\{v_{2},w_{2}\}$ . Depicted in addition are a vertex subset $S=\{s_{1},s_{2},s_{3},s_{4}\}$ (solid black vertices) and the connected components of the graph $G[V\setminus S]$ induced by the complement of $S$ (green areas). All interactions except $\{u_{1},u_{3}\}$ and $\{w_{2},w_{3}\}$ are separated by $S$ in $G$ , i.e., they belong to $F(S)$ . In the multi-separator problem , vertex separation is considered for all interactions, whether these are edges or non-edges.

Panel of Figure 2 — Figure 2: Depicted above is a graph $G$ , along with two vertex subsets, $A=\{a\}$ and $B=\{b_{1},b_{2},b_{3}\}$ (in green). There are three minimal $\{A,B\}$ -connectors of $G$ : $\{a,u_{1},b_{1}\}$ , $\{a,u_{2},b_{2}\}$ and $\{a,u_{2},u_{3},b_{3}\}$ . All the minimal $\{A,B\}$ -separators of $G$ are given by $\{a\}$ , $\{u_{1},u_{2}\}$ , $\{b_{1},b_{2},b_{3}\}$ , $\{u_{2},b_{1}\}$ , $\{u_{1},u_{3},b_{2}\}$ , $\{b_{1},b_{2},u_{3}\}$ and $\{u_{1},b_{2},b_{3}\}$ . Notice that $\{u_{1},u_{2}\}$ is the only minimal $\{A,B\}$ -separator of $G$ that is disjoint from $A$ and $B$ .

Panel of Figure 3 — Figure 3: Depicted above are graphs (black) together with interactions (green, dashed) where some condition of Theorem 1 or Theorem 2 is violated for a vertex or interaction. 3a) Since $u$ is a neighbor of $v$ and $\{u,v\}\in F$ , Condition (i) of Theorem 1 is violated, and thus, the lower box inequality $x_{v}\geq 0$ is not facet-defining. 3b) Since $u$ is a $\{v,w\}$ -cut-vertex, Condition (ii) of Theorem 1 is violated, and thus, the lower box inequality $x_{v}\geq 0$ is not facet-defining. 3c) Since both $v$ and $w$ are $\{u,u^{\prime}\}$ -cut-vertices, the condition in Theorem 2 is violated, and thus, the upper box inequality $x_{\{v,w\}}\leq 1$ is not facet-defining.

Panel of Figure 4 — Figure 4: Depicted above are graphs $G=(V,E)$ (black, solid) and interactions $F$ (green, dashed) with ${\{p,q\}}\in F$ . In each of these graphs, there exists a ${\{p,q\}}$ -connector $C$ that violates one condition of Theorem 4 . Thus, the connector inequality with respect to $\{p,q\}$ and $C$ is not facet-defining for $\Xi_{GF}$ . Written below each of the depicted graphs is an inequality satisfied by all feasible vectors for this graph. These inequalities are examples of the inequalities constructed in the proof of Theorem 4 to establish necessity of the respective conditions. 4a) Condition (i) is violated for $C=\{p,c_{1},q\}$ as $\{p,q\}\subset C$ is a ${\{p,q\}}$ -connector. 4b) Condition (ii) is violated for $C=\{p,c_{1},q\}$ as $\{p,c_{1}\}\in F$ . 4c) Condition (iii) is violated for $C=\{p,c_{1},q\}$ as $u$ is a $c_{1}$ -bypass and $\{u,c_{1}\}\in F$ . 4d) Condition 4 is violated for $C=\{p,c_{1},q\}$ as $\{u,w\},\{u,c_{1}\}\in F$ and $w$ is both a $c_{1}$ -bypass and a $\{\{u\},C\}$ -cut-vertex. 4e) Condition (v) is violated for $C=\{p,c_{1},c_{2},c_{3},c_{4},q\}$ as $\{u,c_{2}\},\{u,c_{3}\}\in F$ and the set $\{v,v^{\prime}\}$ of $c_{2}$ - and $c_{3}$ -bypasses is a $\{\{u\},C\}$ -separator.

Panel of Figure 5 — Figure 5: Depicted above are a graph $G$ (solid black), a designated interaction $f=\{p,q\}$ (dashed red), and other interactions $vs_{1},vp,vq,us_{2},uw,s_{1}s_{2},qw$ (dashed green). The set $S=\{s_{1},s_{2}\}$ is a minimal $f$ -separator of $G$ . All interactions except $qw$ are in $F(S)$ . The subgraph $G(S,s_{1})$ is induced by $\{p,u,s_{1},v,w,q\}$ . The subgraph $G(S,s_{2})$ is induced by $\{p,u,s_{2},w,q\}$ . Moreover, $S(f)=S(uw)=S$ , $S(vs_{1})=S(vp)=S(vq)=\{s_{1}\}$ , $S(us_{2})=\{s_{2}\}$ , and $S(s_{1}s_{2})=\varnothing$ .

Panel of Figure 6 — Figure 6: Examples illustrating the conditions of Corollary 5 . Each subfigure depicts a graph $G$ (solid black) together with the interactions (dashed) defining a valid inequality $x_{g}\leq x_{f}$ . Neither inequality is facet-defining: In 6a) , condition (i) is violated by $f^{\prime}$ (highlighted in red), while in 6b) , condition (ii) is violated by $f^{\prime}$ and $f^{\prime\prime}$ (highlighted in red). For each subfigure, we additionally list an equality satisfied by all feasible vectors in the face induced by the corresponding inequality.

Panel of Figure 7 — Figure 7: Each subfigure depicts a graph $G$ (solid black), interactions (dashed edges), a designated interaction $f=pq$ (dashed, red), and a minimal $f$ -separator $S$ (filled black vertices). In each case, the separator inequality associated with $f$ and $S$ does not define a facet because either Condition (iii) or (iv) is violated, though Conditions (i) and (ii) are satisfied. This fact can also be confirmed by the additional equalities listed below the subfigures. 7a) All the vertices are degenerate and $f_{1}$ is the only edge of $\mathcal{H}(f,\{s\})$ . Condition (iii) is violated by the degenerate vertex $v$ , though it is a leaf of $\mathcal{H}(f,\{s\})$ . As both endvertices of $f_{1}$ are degenerate, Condition (iv) also does not hold. 7b) The only degenerate vertices are $s_{1}$ , $s_{2}$ , $p$ , $q$ and the edge set of $\mathcal{H}(f,S)$ consists of $f_{1}$ and $f_{2}$ . The unique non-isolated vertex $v$ of $\mathcal{H}(f,S)$ separated from $f$ by $S=\{s_{1},s_{2}\}$ in $G$ is $v$ , it is non-degenerate but not a leaf of $\mathcal{H}(f,S)$ , so Condition (iii) of Theorem 5 is violated by $v$ . Thus the corresponding separator inequality is not facet-defining. However, $\mathcal{H}(f,S)$ satisfies Condition (iv) . 7c) The only degenerate vertices are $v$ , $s_{1}$ , $s_{2}$ , $p$ , $q$ and the only edge of $\mathcal{H}(f,\{s_{1},s_{2}\})$ is $f_{3}$ . It is direct to see that Condition (iii) is satisfied as no vertices are separated from $f$ by $S=\{s_{1},s_{2}\}$ in $G$ . The odd path $\mathcal{H}(f,\{s_{1},s_{2}\})$ has two degenerate endvertices and hence Condition (iv) is false. 7d) All the vertices are degenerate and $f_{2}$ is the only edge of $\mathcal{H}(f,\{s_{1},s_{2}\})$ . As no vertices of $\mathcal{H}(f,\{s_{1},s_{2}\})$ are separated from $f$ by $S$ in $G$ , Condition (iii) is vacuously true. However, Condition (iv) is not satisfied as the two leaves, i.e. the endvertices of $f_{2}$ , of the odd path $\mathcal{H}(f,\{s_{1},s_{2}\})$ are degenerate. 7e) In this example, $s_{1}$ , $s_{2}$ , $p$ , $q$ are all the degenerate vertices and the edge set of $\mathcal{H}(f,\{s_{1},s_{2}\})$ is $\{f_{1},f_{2},f_{3}\}$ . Condition (iii) is vacuously true due to the same reason as in the previous case. $\mathcal{H}(f,\{s_{1},s_{2}\})$ is an odd path whose two endvertices are degenerate and hence violates Condition (iv) . 7f) The only degenerate vertices are $s_{1}$ , $s_{2}$ , $p$ , $q$ and the edge set of $\mathcal{H}(f,\{s_{1},s_{2}\})$ consists of $f_{1}$ , $f_{2}$ , $f_{3}$ and $f_{4}$ . As the previous case, Condition (iii) is vacuously true. On the other hand, $\mathcal{H}(f,\{s_{1},s_{2}\})$ is an even cycle and hence Condition (iv) is violated. 7g) The degenerate vertices in this case include $v$ and $v^{\prime}$ besides $f$ -cut-vertices $p$ , $q$ and the vertices $s_{1}$ , $s_{2}$ in the separator $S$ . The edge set of $\mathcal{H}(f,S)$ consists of $f_{1}$ and $f_{2}$ . As no vertices are separated from $f$ by $S$ in $G$ , Condition (iii) is trivially satisfied. Condition (iv) is violated because $\mathcal{H}(f,S)$ is an even path with two degenerate endvertices $v$ , $v^{\prime}$ . 7h) The only degenerate vertices are $f$ -cut-vertices $p$ , $q$ and $v$ , besides those in $S$ . The edges of $\mathcal{H}(f,S)$ are given by $f_{1}$ , $f_{2}$ , $f_{3}$ and $f_{4}$ . Again, as no vertices are separated from $f$ by $S$ in $G$ , Condition (iii) is trivially satisfied. $\mathcal{H}(f,S)$ is an even path with two endvertices $p$ and $v$ being $f$ -cut-vertices of $G$ , so Condition (iv) is violated.

Panel of Figure 8 — Figure 8: Each subfigure shows a graph $G$ (solid black) with interactions (dashed green) and a path $P$ on vertices $\{s,v,t\}$ . In 8a) , the $st$ -connector inequality $x_{st}\leq x_{s}+x_{v}+x_{t}$ is not facet-defining by Theorem 4 (ii) , whereas the path inequality $x_{st}\leq x_{sv}+x_{vt}-x_{v}$ is facet-defining by Theorem 6 . In 8b) , the connector inequality $x_{st}\leq x_{s}+x_{v}+x_{t}$ is not facet-defining by Theorem 4 (i) , whereas the path inequality $x_{st}\leq x_{sv}-x_{v}+x_{vt}$ is facet-defining by Theorem 6 .

Panel of Figure 9 — Figure 9: An illustration of the intersection inequality ( 8 ) with $G$ depicted in solid black: the crossing pairs $(v_{1},w_{1})$ and $(v_{2},w_{2})$ (in red) versus the parallel pairs $(v_{1},w_{2})$ and $(v_{2},w_{1})$ (in green).

Panel of Figure 10 — Figure 10: Depicted above are graphs $G$ (solid) and interactions $F$ (both solid and dashed). Vertices and interactions with coefficients $+1$ and $-1$ in the odd-cycle inequalities ( 10 ) are depicted in red and green, respectively. The odd-cycle inequality associated with the cycle in 10a) is not valid for the corresponding multi-separator polytope $\Xi_{GF}$ , which can be seen by looking at the feasible vector $x^{\{v_{0},v_{1},v_{3}\}}$ . Each of the odd-cycle inequalities associated with the colored cycles in 10b) , 10c) , 10d) and 10e) is valid but not facet-defining for $\Xi_{GF}$ due to the existence of extra interactions. More specifically, in 10b) we have the additional equality $x_{v_{5}}+x_{v_{0}v_{4}}=x_{v_{0}v_{5}}+x_{v_{4}v_{5}}$ containing the face defined by the corresponding odd-cycle inequality. Similarly, the additional inequalities $x_{v_{2}v_{5}}=x_{v_{3}v_{4}}$ , $x_{v_{0}v_{3}}=1$ , and $x_{uv_{1}}=x_{uv_{2}}$ are satisfied in 10c) , 10d) , and 10e) , respectively. The odd-cycle inequality associated with the colored cycle in 10f) is valid and facet-defining for $\Xi_{GF}$ .

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 11 — Figure 11: Examples illustrating the constructions in Lemma 7 . Depicted are graphs $G$ (solid, black) and interactions $F$ (dashed, green).

Panel of Figure 12 — Figure 12: Depicted above are graphs $G$ (black, solid), interactions (green, dashed) and a specified vertex $v$ , which defines a lower box inequality $x_{v}\geq 0$ . Both conditions (i) and (ii) are satisfied. Case (B) in Section D.7 applies to 12a) , where the required minimal $f$ -connector can be chosen as $C=\{u,r,w\}$ . Case (C) in Section D.7 applies to 12b) and 12c) , where the required minimal $f$ -connectors can be chosen as $C=\{u,r,w\}$ and $C=\{u,u^{\prime},w\}$ , respectively. Note that $u^{\prime}$ is the unique vertex of $C$ that is adjacent to $v$ in $G$ in both 12b) and 12c) . The set $F_{AB}$ constructed in case (C) is $\{f\}$ for 12b) and $\{f,f^{\prime}\}$ for 12c) .

Panel of Figure 13 — Figure 13: This figure illustrates the construction of the characteristic vector in ( 44 ) for $\alpha\neq\beta$ . Consider the graph $G=(V,E)$ depicted above in solid black and the $f$ -connector $C=\{c_{0},\dots,c_{5}\}$ for $f=c_{0}c_{5}$ . Here it holds that $\alpha=1$ and $\beta=4$ . Suppose that the set of interactions is $F=\binom{V}{2}$ . Depicted in 13a) , 13b) , and 13c) in dashed green are the characteristic vectors $\mathbbm{1}_{F_{AB}}$ , $\mathbbm{1}_{F_{AB(c_{\alpha})}}$ , and $\mathbbm{1}_{F_{AB(c_{\beta})}}$ , respectively. Depicted in 13d) in dashed green is the characteristic vector of the interaction set $\{uw\in F\mid w\in\textnormal{BP}_{v}\}$ that is constructed in ( 44 ).

Panel of Figure 14 — Figure 14: This figure illustrates the construction of the characteristic vector in ( 44 ) for $\alpha=\beta$ . Consider the graph $G=(V,E)$ depicted above in solid black and the $f$ -connector $C=\{c_{0},c_{1},c_{2}\}$ for $f=c_{0}c_{2}$ . Here it holds that $\alpha=\beta=1$ . Suppose that the set of interactions is $F=\binom{V}{2}$ . Depicted in 14a) and 14b) in dashed green are the characteristic vectors $\mathbbm{1}_{F_{AB}}$ and $\mathbbm{1}_{F_{AB(c_{\alpha})}}$ , respectively. Depicted in 14c) in dashed green is the characteristic vector of the interaction set $\{uw\in F\mid w\in\textnormal{BP}_{v}\}$ that is constructed in ( 44 ). Notice that we have $\textnormal{BP}_{v}=\{v\}$ as $v$ is not a $C$ -bypass.

Panel of Figure 15 — Figure 15: This figure illustrates the construction of the characteristic vector in ( 48 ) of case (B) . Consider the graph depicted above in solid black and the $f$ -connector $C=\{c_{0},\dots,c_{5}\}$ for $f=c_{0}c_{5}$ . Let $w=c_{2}\notin\textnormal{BP}_{v}$ . Then the unique vertex $w^{\prime}$ defined in the proof of Claim 1 is $w^{\prime}=c_{1}$ . Suppose that the set of interactions is $F=\binom{V}{2}$ . Depicted in 15a) and 15b) in dashed green are the characteristic vectors $\mathbbm{1}_{F_{AB(w)}}$ and $\mathbbm{1}_{F_{AB(w^{\prime})}}$ , respectively. Depicted in 15c) in dashed green is the characteristic vector $\mathbbm{1}_{\{uw\}}$ that is constructed in ( 48 ).

Panel of Figure 16 — Figure 16: Depicted above are examples illustrating the constructions in the proof of Claim 2 . Each figure consists of a graph $G$ (solid black), a designated interaction $f=pq$ (dashed red), a minimal $f$ -separator $S=\{s\}$ of $G$ , and other interactions (dashed green). In 16a) , if $C_{1}=\{p,s\}$ , $C_{2}=\{s,w,w_{1},q\}$ , $C^{\prime}_{1}=\{u\}$ and $C^{\prime}_{2}=\{w\}$ , then $U=\{u,p,s,w,w_{1},q\}$ , $A=U\setminus\{u\}$ and $B=U\setminus\{s\}$ . Thus, $F_{AB}=\{up,us,uw,uw_{1}\}$ and $[uw]_{s}=\{us,uw\}$ . In 16b) , if $C_{1}=\{p,u_{1},u,s\}$ , $C_{2}=\{s,w,w_{2},q\}$ , $C^{\prime}_{1}=\{u\}$ and $C^{\prime}_{2}=\{w\}$ , then $U=\{p,u_{1},u,s,w,w_{2},q\}$ , $A=U\setminus\{s\}$ and $B=U$ . Thus, $Q_{AB}=\{uw,u_{1}w,uw_{2},sw_{2},s,f\}$ , $[uw]_{s}=\{s,f,uw\}$ , $[u_{1}w]_{s}=\{u_{1}w\}$ , and $[uw_{2}]_{s}=\{uw_{2},sw_{2}\}$ .

Panel of Figure 18 — Figure 18: Depicted above are examples illustrating the notion $\langle v\rangle$ . Each figure consists of a graph $G$ (solid black), a designated interaction $f=pq$ (dashed red), a minimal $f$ -separator $S=\{s_{1},s_{2}\}$ of $G$ , and other interactions (dashed green). In 18a) , $[f^{\prime}]_{s_{1}}=\{f^{\prime},f^{\prime\prime}\}=[f^{\prime}]_{s_{2}}$ , hence $\langle v\rangle=[f^{\prime}]_{s_{1}}=[f^{\prime}]_{s_{2}}$ . As a comparison, we have $[f^{\prime}]_{s_{1}}=\{f^{\prime},f^{\prime\prime}\}$ and $[f^{\prime}]_{s_{2}}=\{f^{\prime},f^{\prime\prime},vs_{2}\}$ in 18b) , hence $\langle v\rangle=[f^{\prime}]_{s_{1}}\neq[f^{\prime}]_{s_{2}}$ .

Panel of Figure 19 — Figure 19: Examples of the constructions in the proof of Theorem 6 . Each subfigure consists of a graph $G$ (solid black) , a path $P$ on the vertex set $\{v_{0},v_{1},v_{2},v_{3},v_{4}\}$ , and interactions (dashed green). In 19a) , the paths induced by the edges $sv_{1}$ and $tv_{3}$ can be chosen as $P^{\prime}$ and $P^{\prime\prime}$ respectively; in 19b) , the path induced by any of the edges $sv_{0}$ , $sv_{1}$ , $sv_{3}$ can be chosen as $P^{\prime}$ .

Panel of Figure 20 — Figure 20: Depicted are graph (solid black) and interactions (dashed). In each subfigure, the green interactions define an intersection equality. For each red interaction, its corresponding standard unit vector is constructed in the proof of Theorem 7 .

Combinatorial Optimization

Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.

See all 384 papers

Graph Neural Networks with Triangle-Based Messages for the Multicut Problem
May 13, 2026Jannik Irmai, Lucas Fabian Naumann, Bjoern AndresGraph Neural Networks Combinatorial Optimization
Faculty of Computer Science, TU Dresden · Center for Scalable Data Analytics and AI, Dresden/Leipzig
Normalized Cuts and Data Clustering via Matrix Fractional Programming
Oct 27, 2026Yannan Chen, Beichen Huang, Licheng Zhao +2Clustering Graph Clustering
Key Laboratory of Radio Frequency Heterogeneous Integration, Shenzhen University, Shenzhen 518060, China · School of Science and Engineering, The Chinese University of Hong Kong (Shenzhen), Shenzhen 518172, China · Beichen Huang is an undergraduate student at McMaster University, Canada +2
Graph Partitioning with Demands: Generalized Conductance and its Applications
Jul 14, 2026Michał Szyfelbein, Dariusz DereniowskiHierarchical Clustering Approximation Algorithms
Gdańsk University of Technology

May 13, 2026J/K move · Enter open · S save

Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

Jannik Irmai, Lucas Fabian Naumann, Bjoern Andres

Faculty of Computer Science, TU Dresden · Center for Scalable Data Analytics and AI, Dresden/Leipzig

Graph Neural Networks Combinatorial Optimization Message Passing Neural Networks Neural Combinatorial Optimization

Open paper AskPDF arXiv

The multicut problem is an NP-hard combinatorial optimization problem with diverse applications in fields such as bioinformatics, data mining and computer vision. Graph neural networks have been defined for the multicut problem but can be adapted further to its specific objective function and constraints. In this article, we introduce such an adapted graph neural network architecture in which features are assigned only to edges, and the computation of messages is based on triangles in the underlying graph. Experiments with synthetic and real-world instances with up to 200 nodes show that our method outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. For some instances, our method finds optimal solutions in seconds whereas exact solvers need hours to find and certify optimal solutions.

Abstract

Combinatorial Optimization

Explore similar work

Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

Normalized Cuts and Data Clustering via Matrix Fractional Programming

Graph Partitioning with Demands: Generalized Conductance and its Applications