PaperlayerView exact revision on arXiv

Source-linked AI summary

The canonical facets of multi-separator polytopes

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

arXiv:2608.16861v1cs.DMcs.LGmath.CO

TL;DR

The graph multi-separator problem lacks a polyhedral characterization despite its proposal as an alternative to lifted multicut for image segmentation. This paper studies its ILP-defined polytope, characterizes facets through graph conditions, strengthens inequalities, and derives a totally dual integral path description.

  • Problem

    The graph multi-separator problem lacks a polyhedral characterization, although it was proposed as an alternative to lifted multicut for image segmentation.

  • Method

    The paper analyzes the ILP-defined multi-separator polytope, characterizes facets using graph-theoretic conditions, strengthens inequalities, and relates the polytope to two others.

  • Results

    The paper gives efficiently decidable facet conditions, a totally dual integral path description, and projection-of-a-face relations with the lifted multicut polytope.

  • Takeaways & Limitations

    These results establish efficiently testable polyhedral structure for multi-separator polytopes and clarify its relationships with boolean quadric and lifted multicut polytopes.

  • Takeaways & Limitations

    Odd-cycle facets from the boolean quadric polytope do not generally transfer, and corresponding inequalities may fail validity for multi-separator polytopes.

Abstract

from arXiv · show

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.

1 Introduction

The multi-separator problem minimizes costs for selected vertices and separated prescribed pairs, extending several graph optimization problems and serving as an alternative to lifted multicuts for image segmentation. This article develops its ILP and polyhedral theory, characterizing canonical and strengthened facets, proving a path-case totally dual integral description, and relating the resulting polytope to boolean quadric and lifted multicut polytopes.

  • Problem formulation: The multi-separator problem selects vertex subsets and accounts for long-range interactions between prescribed pairs based on whether those pairs remain connected after vertex removal.Its objective minimizes the costs of selected vertices and separated interaction pairs.
  • Motivation and relationships: The problem generalizes quadratic unconstrained binary optimization, node-weighted Steiner trees, and multi-terminal vertex separators, while providing an alternative to lifted multicuts for image segmentation.For certain cost patterns, it is also less complex than the lifted multicut problem.
  • Polyhedral contributions: The article formulates the problem as an integer linear program and characterizes its canonical polytope facets through efficiently decidable graph-theoretic conditions.These are the facets induced by inequalities of the ILP.
  • Polyhedral contributions: The study strengthens ILP inequalities and identifies additional facets of some multi-separator polytopes induced by those stronger inequalities.It also gives a totally dual integral description for paths when separation is considered for all vertex pairs.

2 Related work

Prior work studies several vertex-separator variants through integer programming and polyhedral analysis, including generalized, k-separator, vertex k-cut, and multi-terminal formulations. The multi-separator polytope is related to the boolean quadric, lifted multicut, and Steiner tree polytopes, but its separator inequalities have distinct facet structures.

  • Vertex-separator variants: Generalized vertex separator research seeks a vertex subset leaving at most β components, each of cardinality at most κ, with a polyhedral analysis based on matrix decomposition.The parameters β and κ are positive constants.
  • Vertex-separator variants: The k-separator problem minimizes vertex-subset weight subject to every remaining connected component having size at most k, while related vertex k-cut work requires at least k components.Both problem families have been studied through alternative ILP formulations and valid inequalities.
  • Multi-terminal separation: Multi-terminal vertex separation prescribes terminals and seeks a minimum-weight deletion set leaving exactly one terminal in each connected component, with its ILP polyhedral structure supporting a branch-and-cut algorithm.This formulation was studied by Cornaz et al. (2019b).
  • Related polytopes: The boolean quadric polytope is a special case of the multi-separator polytope for adjacent vertex pairs, while the lifted multicut polytope is its edge-based counterpart.The lifted multicut problem generalizes the multicut problem, and both relations are discussed later in the paper.
  • Facet structures: Although separator inequalities resemble lifted-multicut cut inequalities and Steiner cut inequalities, their facet behavior differs: lifted-multicut facet recognition is NP-hard, whereas Steiner cut inequalities are always facet-defining.The paper also states that facet-defining conditions for multi-separator separator inequalities are more complicated than minimal-separator conditions for related connectivity inequalities.

3 Preliminaries

This section establishes connector and separator terminology for vertex subsets and characterizes their inclusion-minimal forms. Minimal connectors induce paths between the specified sets, while minimal separators intersect every such connector essentially.

  • Definitions: An {A, B}-connector contains an a–b connector for some a ∈ A and b ∈ B, whereas an {A, B}-separator separates every such pair.An {A, B}-separator is equivalently a set whose complement is not an {A, B}-connector.
  • Minimal structures: A minimal {A, B}-connector induces a path whose endpoints are the only vertices it shares with A and B, respectively.The induced path may consist of a single vertex when its length is zero.
  • Minimal structures: A minimal {A, B}-separator intersects every minimal {A, B}-connector, with each separator vertex uniquely hit by at least one connector.This gives an inclusion-minimal characterization of separators through the family of minimal connectors.
  • Vertex-pair specialization: For vertex pairs, minimal connectors are exactly paths, and minimal separators meet every path while each separator vertex lies on a path meeting the separator only there.A pairwise minimal separator is either an endpoint singleton or has a complement inducing disconnected components containing the two endpoints separately.

4 Multi-separator polytopes

This section develops the polyhedral structure of multi-separator polytopes, establishing polynomially separable canonical relaxations, full dimensionality, and graph-theoretic characterizations of several facet classes. It also identifies stronger valid inequalities, including path inequalities that strengthen connector inequalities.

  • Canonical relaxation: The canonical inequalities define a linear relaxation with the same integer feasible solutions as the multi-separator problem, and their separation is polynomial-time solvable.Box separation is trivial, while connector and separator separation algorithms are provided separately.
  • Polytope structure: For connected graphs with arbitrary interaction sets, the multi-separator polytope is full-dimensional, with dimension |V ∪ F|, so each facet has a unique defining inequality up to positive scaling.For disconnected graphs, the polytope decomposes, up to translation, as a product of the polytopes on connected components, and facets correspond componentwise.
  • Canonical facets: Canonical facet inequalities are characterized by the number of interaction variables with nonzero coefficients: at most one is necessary and sufficient for a facet-defining inequality to be canonical, up to positive scaling.This characterization relies on full dimensionality and applies to facet-defining inequalities with integer coefficients.
  • Box facets: Box facets are governed by graph structure: interaction lower bounds never define facets, while the remaining vertex and interaction bounds are facet-defining exactly under stated cut-vertex conditions.The conditions distinguish vertex lower bounds, vertex upper bounds, and interaction upper bounds.
  • Connector and separator facets: Connector and separator inequalities are facet-defining precisely under finite graph-theoretic conditions involving minimality, bypasses, cut-vertices, separators, and the structure of an associated forest.The conditions for separator facets can be checked in polynomial time, enabling efficient certification.
  • Strengthened inequalities: The section strengthens ordinary separator and connector inequalities: additional valid terms can produce stronger separator inequalities, and path inequalities are valid for every interaction and path and strengthen connector inequalities.Path inequalities are introduced as a class of valid inequalities whose facet-defining conditions are characterized subsequently.

5 Related polytopes

The section relates the multi-separator polytope to the boolean quadric and lifted multicut polytopes. It establishes conditional inequality transfers, shows odd-cycle facets need not transfer generally, and proves mutual projection relationships, including a path case with a totally dual integral description.

  • Boolean quadric polytope: Valid inequalities transfer between boolean quadric and multi-separator polytopes under coefficient-sign and edge-containment conditions.Lemma 6 also transfers facet-defining inequalities from Ξ_G^F to BQP_G when the nonzero-coefficient interactions lie in E.
  • Boolean quadric polytope: Odd-cycle inequalities do not generally transfer as facets from boolean quadric polytopes to multi-separator polytopes.They may fail validity when cycle edges are interactions but not graph edges, and facet transfer fails when E_C is a strict subset of F_C.
  • Lifted multicut polytope: Every lifted multicut polytope is the projection of a face of a multi-separator polytope on the subdivision of the underlying graph.This is stated for any connected G and any G′ with E ⊆ F.
  • Lifted multicut polytope: Conversely, every multi-separator polytope is the projection of a face of a suitably augmented lifted multicut polytope.The construction subdivides G, adds a new vertex connected to each original vertex, and adds specified interaction edges.
  • Paths: For paths, the multi-separator polytope is equivalent to the lifted multicut polytope, yielding a complete description whose system (16)–(20) is totally dual integral.The path correspondence enables the complete lifted-multicut description from Lange and Andres (2021) to apply to the multi-separator setting.

6 Conclusion

The paper characterizes facet-defining connector, separator, and box inequalities for the multi-separator polytope through efficiently decidable graph-theoretic conditions. It strengthens the relaxation with path and intersection inequalities, obtains a totally dual integral description for certain path graphs, and relates the polytope to the boolean quadric polytope.

  • Efficiently decidable graph-theoretic conditions characterize when connector inequalities define facets of the multi-separator polytope.
  • The same conditions characterize facet-defining separator and box inequalities for the multi-separator polytope.
  • Path and intersection inequalities provide a tighter polyhedral relaxation of the multi-separator polytope.
  • For path graphs in which every vertex pair forms an interaction, the strengthened inequalities yield a totally dual integral description.
  • Facets induced by odd-cycle inequalities in the boolean quadric polytope do not generally transfer to the multi-separator polytope.

A Separation algorithms

The section gives efficient separation procedures for connector and separator inequalities. Connector violations reduce to shortest-path searches, while separator violations reduce to minimum-cut computations in an auxiliary graph.

  • A Separation algorithms: Connector inequalities are separable by searching for shortest paths, and separator inequalities by solving a max-flow problem in an auxiliary graph.
  • A Separation algorithms: O(|E||V| + |V|^2log|V|) time suffices to decide whether a violated connector inequality exists and return one.Dijkstra’s algorithm computes shortest f-paths for all interactions within this bound.
  • A Separation algorithms: A connector inequality for interaction f is violated exactly when a minimum-weight f-path P satisfies w(P) + 1/2(x_s + x_t) < x_f.
  • A Separation algorithms: A violated separator inequality exists exactly when the minimum (u′, v′′)-cut in the auxiliary graph has value below 1 − x_f.The auxiliary graph assigns weights 1 − x_s to vertex arcs and weight 2 to all other arcs.
  • A Separation algorithms: Dinic’s algorithm computes the auxiliary minimum cut in time O(|V′|^2|E′|), with |V′| = 2|V| and |E′| = |V| + 2|E|.

B Construction of feasible vectors … D.1 Proof of Proposition 1

The appendix develops algebraic constructions for feasible vectors, characterizes full-rank incidence matrices through pseudoforests, and proves graph-theoretic conditions for minimal connectors and separators. These tools support facet sufficiency arguments for multi-separator polytopes.

  • B Construction of feasible vectors: Lemma 7 constructs vectors in the linear space generated by feasible-vector differences when x_A, x_B, x_{A∩B}, and x_{A∪B} are feasible.The construction uses the sets Q_AB, F_AB, and H_AB to define the resulting vectors.
  • B Construction of feasible vectors: When A ⊆ B and B \ A = {b}, Q_AB consists of b and interactions for which b is an f-cut-vertex of G[B], while F_AB and H_AB are empty.For singleton differences on both sides, F_AB identifies interactions where both differing vertices are cut-vertices, and H_AB identifies minimal separator conditions.
  • C Dimension and pseudoforests: The appendix introduces loop graphs and pseudoforests, with a pseudoforest characterized by every induced subgraph having at most as many edges as vertices.These notions connect graph structure to incidence-matrix rank.
  • C Dimension and pseudoforests: The incidence matrix of a loop graph has full column rank if and only if the graph is a pseudoforest without even cycles.This is the central rank characterization used in the dimension analysis.
  • D.1 Proof of Proposition 1: For Part (i), a minimal A,B-connector U induces a path whose endpoints are the unique vertices of U in A and B, and the converse also holds.Minimality forces the connector to use all vertices of U; a path with the stated endpoint condition has no smaller connector.
  • D.1 Proof of Proposition 1: For Part (ii), U is a minimal {A,B}-separator exactly when every minimal {A,B}-connector intersects U in a common single vertex.If no such common vertex exists, one can remove a vertex while preserving separation, contradicting minimality.

D.2 Proof of Lemma 1 · D.3 Proof of Proposition 2

The proofs establish the multi-separator ILP characterization by reducing feasibility to connector–separator equivalences and minimal structures. They also show that vertex and interaction unit vectors lie in the affine-hull linear space through separate constructions.

  • D.2 Proof of Lemma 1: The lemma identifies XGF exactly as the binary vectors satisfying inequalities (1), (2), and (3).The proof first notes feasibility implies all three inequality families, then proves the converse.
  • D.2 Proof of Lemma 1: For each interaction f, xf = 0 is equivalent to every f-separator containing a zero-labeled vertex and some f-connector being entirely zero-labeled.The implications use separator inequalities for (A)⇒(B), a contradiction argument for (B)⇒(C), and connector inequalities for the remaining direction.
  • D.2 Proof of Lemma 1: Only minimal f-connectors and minimal f-separators need explicit inequalities, because each stronger inequality implies the corresponding inequality for every containing non-minimal structure.Thus inequalities associated with non-minimal connectors and separators are redundant in the linear relaxation.
  • D.3 Proof of Proposition 2: Proposition 2 reduces the affine-hull claim to proving 1{g} ∈ lin(XGF − XGF) for every vertex or interaction g.The proof treats vertices and interactions separately.
  • D.3 Proof of Proposition 2: For a vertex v, choosing A = {v} and B = ∅ yields QAB = {v}, so Lemma 7 implies 1{v} belongs to the affine-hull linear space.The construction relies on interactions having two distinct endvertices, making {v} an f-connector for no interaction.
  • D.3 Proof of Proposition 2: For an interaction f = {u, w}, a minimal f-connector U produces sets A = U \ {u} and B = U \ {w} with FAB = {f}.Minimality ensures neither A nor B is an f-connector while their union is, and any interaction in FAB must equal f.

D.4 Proof of Proposition 3 · D.5 Proof of Proposition 4 · D.6 Proof of Proposition 5

The proofs establish that facet-defining inequalities with at most one nonzero interaction coefficient are canonical, while also deriving the product decomposition of the polytope and basic redundancy relations among its inequalities.

  • D.4 Proof of Proposition 3: If |F(a)| ≤ 1, every facet-defining inequality is canonical, with the cases F(a) = ∅ and |F(a)| = 1 handled separately.The proof begins by reducing the sufficiency claim to these two cases.
  • D.4 Proof of Proposition 3: When F(a) = ∅, the inequality is a nonnegative combination of box inequalities and therefore reduces to a single box inequality.The possible nonzero vertex-coefficient patterns are one positive coefficient or one negative coefficient.
  • D.4 Proof of Proposition 3: When |F(a)| = 1 and the interaction coefficient is positive, facetness forces the negative-support vertices to form an f-connector, yielding a connector inequality.A max-flow min-cut argument expresses the inequality as a nonnegative combination of connector and box inequalities.
  • D.4 Proof of Proposition 3: When |F(a)| = 1 and the interaction coefficient is negative, facetness forces the positive-support vertices to form an f-separator, yielding a separator inequality.A max-potential min-work argument decomposes the inequality into separator and box inequalities.
  • D.5 Proof of Proposition 4: Interactions in F(∅) are always labeled 1, while every other interaction label is determined by the connected component containing its endpoints; hence ΞGF decomposes as a polytope product.The remaining assertion follows from the basic product property of polytopes.
  • D.6 Proof of Proposition 5: The separator inequality xv ≤ xf for an interaction f = {u,v} implies xf ≥ 0 whenever xv ≥ 0.This proves the first stated implication using that {v} is an f-separator.
  • D.6 Proof of Proposition 5: For an edge {u,v} incident with v, connector and separator inequalities imply xv ≥ 0 and xv ≤ 1 under xuv ≤ 1.Specifically, xuv ≤ xu + xv together with xu ≤ xuv gives the lower bound, while xv ≤ xuv gives the upper bound.

D.7 Proof of Theorem 1

Theorem 1 proves that the lower box inequality x_v ≥ 0 is facet-defining exactly when conditions (i) and (ii) hold. Necessity follows from additional equalities when either condition fails, while sufficiency follows by showing the equality face has codimension one.

  • Face characterization: Every feasible vector on the face x_v = 0 is the incidence vector x_U of a vertex subset U containing v.This identifies the face with feasible subsets containing v.
  • Necessity: If condition (i) fails, an adjacent interaction forces x_{\{u,v\}} = x_u throughout the face, so x_v ≥ 0 cannot define a facet.The equality follows from the separator and connector inequalities.
  • Necessity: If condition (ii) fails, the face satisfies x_{\{v,w\}} = x_{\{u,w\}} for the specified vertices, yielding an equality independent of x_v = 0.The argument uses connector sets and the assumptions that {u,v} ∈ E and {v,w}, {u,w} ∈ F.
  • Sufficiency: When conditions (i) and (ii) hold, all standard unit vectors for vertices other than v lie in lin(X′ − X′).For a vertex v′ ≠ v, the proof uses A = {v}, B = {v,v′} and Lemma 7.
  • Sufficiency: The interaction coordinates are likewise generated by considering f-paths and minimal f-connectors in cases (A), (B), and (C).Case (A) directly produces the interaction unit vector, while cases (B) and (C) cover the remaining connector configurations.
  • Conclusion: The resulting basis has codimension 1, proving that x_v ≥ 0 defines a facet of the multi-separator polytope under conditions (i) and (ii).The basis consists of unit vectors for every vertex other than v and every interaction.

D.8 Proof of Theorem 2

The proof characterizes when the face xf = 1 is a facet of the multi-separator polytope: precisely when f is not a pair of f′-cut-vertices for any other interaction f′. Sufficiency follows by constructing enough independent directions to show the associated linear space has codimension 1.

  • Face characterization: The equality face X′ = {x ∈ XGF | xf = 1} consists exactly of incidence vectors xU for vertex subsets U whose complements are f-separators.This identifies all feasible vectors on the face with subsets that are not f-connectors.
  • Necessity: If f is a pair of f′-cut-vertices for another interaction f′, then xf ≤ xf′ forces xf′ = 1 throughout X′, so the face is not a facet.The additional equality makes the face fail the facet criterion from Proposition 2.
  • Sufficiency: Conversely, assuming no such f′ exists, the proof constructs a basis of cardinality |V| + |F| − 1 for lin(X′ − X′).This construction supplies the required independent directions for the sufficiency argument.
  • Sufficiency: Vertex-based and interaction-based subset constructions yield unit directions 1{v} and 1{f′} in lin(X′ − X′), establishing codimension 1 and hence facetness.For each interaction f′, a minimal f′-connector containing at most one endpoint of f produces the needed subset relations.

D.9 Proof of Theorem 3

The proof establishes that the face obtained by setting x_v = 1 is a facet exactly when no interaction has v as its cut-vertex. Necessity follows from a separator inequality, while sufficiency constructs basis vectors showing codimension one.

  • Necessity: If some interaction has v as its cut-vertex, the separator and box inequalities force x_f = 1 whenever x_v = 1, so the face is not a facet.This creates an additional equality on the face, preventing facetness.
  • Sufficiency: If no interaction has v as its cut-vertex, minimal connectors avoiding v construct all singleton vertex and interaction directions in lin(X′ − X′).For each interaction f = {u, w}, the connector yields the required set relations and establishes 1_{f} in the associated linear space.
  • Sufficiency: The resulting linear space has codimension 1, and full dimensionality of ΞGF implies that the face defined by x_v = 1 is a facet.The codimension conclusion follows from the constructed basis and Proposition 2.

D.10 Proof of Theorem 4

The proof characterizes when connector inequality (4) defines a facet by showing that conditions (i)–(v) are necessary and constructing a full-dimensional basis under those conditions. The construction uses feasible vectors indexed by vertex subsets and auxiliary characteristic vectors to establish the required linear independence.

  • Structure of X′: The proof represents feasible vectors in X′ as x = x_U for subsets U in V, where C ⊆ U or C \ U is a singleton and U is not an f-connector.The set V is defined so that complements correspond either to sets disjoint from C or to f-separators intersecting C once.
  • Necessity: Conditions (i)–(v) are shown necessary because violating any one makes connector inequality (4) redundant, implied by another valid inequality, or incompatible with equalities on X′.The arguments use minimal connectors, separator inequalities, bypass vertices, and separator constructions to derive contradictions to facet-definingness.
  • Sufficiency: Sufficiency is proved by constructing a basis of cardinality |V|+|F|−1 for lin(X′ − X′).The basis construction relies on auxiliary vectors associated with interactions incident to a vertex and characteristic vectors derived as their linear combinations.
  • Sufficiency: The auxiliary construction uses a minimal uv-connector intersecting NG(C) only at v and distinguishes bypass and non-bypass vertices of C to generate the needed characteristic vectors.The proof verifies the relevant subset memberships and interaction sets before deriving the characteristic-vector relations.
  • Conclusion: The resulting characteristic vectors span every interaction direction required by the construction, and full dimensionality of ΞGF then implies that connector inequality (4) defines a facet.In particular, the proof obtains 1{f′} ∈ lin(X′ − X′) for every interaction f′ in case (G).

D.11 Proof of Theorem 5 … D.14 Proof of Lemma 4

The proofs establish the facet characterization by analyzing the affine dimension of tight feasible vectors, reducing the remaining rank condition to an auxiliary loop graph, and verifying polynomial-time decidability. They also prove supporting structural lemmas and validate a strengthened path inequality through exhaustive value cases.

  • D.11 Proof of Theorem 5: Theorem 5 is proved by showing that conditions (i)–(iv) are necessary and sufficient for separator inequality (5) to define a facet.The argument determines the tight-face dimension through the linear space of feasible vectors satisfying the inequality at equality.
  • D.11 Proof of Theorem 5: Standard unit vectors for vertices outside S and interactions outside F(S) are constructed first, reducing the remaining basis construction to S ∪ F(S).The proof then analyzes equivalence classes of interactions associated with f-cut-vertices.
  • D.11 Proof of Theorem 5: Claim 2 shows that each equivalence-class characteristic vector 1_[f′]_s lies in the relevant linear span, including cases determined by the f-cut-vertex status of f′’s endpoints.This yields the spanning decomposition used to compute the tight-face dimension.
  • D.11 Proof of Theorem 5: The remaining codimension-one condition is equivalent to F∅ = {f}, |⟨v⟩| ≤ 1 for relevant v, and full column rank of the auxiliary loop graph’s incidence matrix.Because its loopless part is bipartite, full column rank is equivalent to the graph being a pseudoforest without cycles of length at least 2.
  • D.12 Proof of Lemma 2: Theorem 5’s conditions are polynomial-time decidable: minimality is checked by testing whether S \ {s} remains an f-separator for every s ∈ S, while the remaining conditions follow from Remark 2.The minimality test is explicitly stated to run in polynomial time.
  • D.13 Proof of Lemma 3: Lemma 3’s sufficiency proof establishes that H(f, S) is acyclic, using three internally vertex-disjoint f-paths to rule out cycles under condition (iii).The proof then considers paths whose only degenerate vertices are their two endpoints.
  • D.14 Proof of Lemma 4: Lemma 4 rewrites the strengthened inequality after multiplying by 2 and proves validity by considering the possible values 0, 1, and 2 of its endpoint expression.For values 1 and 2, the path contains an edge providing the required compensating contribution.

D.15 Proof of Theorem 6 · D.16 Proof of Lemma 5

Theorem 6 proves that the path inequality is facet-defining exactly when the path is chordless after removing its distinguished interaction, while Lemma 5 establishes validity of an intersection inequality under mutual separator conditions. The proofs construct feasible-vector differences to establish codimension one and use connector arguments to verify the intersection inequality.

  • D.15 Proof of Theorem 6: A chord in P outside the distinguished interaction makes inequality (7) non-facet-defining by expressing it as the sum of two valid inequalities.Replacing the corresponding path segment with the chord yields a second distinguished-interaction path, whose valid inequality combines with the path inequality to show redundancy.
  • D.15 Proof of Theorem 6: If P is chordless in (V, F \ {f}), feasible vectors satisfy the path inequality tightly for vertex subsets whose intersection with P is empty or an endpoint-containing subpath.This tightness observation supplies the feasible points used to construct directions in the affine hull of the face.
  • D.15 Proof of Theorem 6: The proof generates standard unit-vector directions for vertices outside P and interactions outside EP ∪ {f}, including interactions with zero, one, or two endpoints on P.For interactions with exactly one endpoint on P, the construction shows 1_{f′} ∈ lin(X′ − X′) for every such interaction.
  • D.15 Proof of Theorem 6: For interior vertices and path edges, the proof obtains the directions 1_{e} + 1_{f} and 1_{v} − 1_{f} from differences of tightly satisfying feasible vectors.These directions complete the span needed to characterize the face.
  • D.15 Proof of Theorem 6: The constructed directions form a basis of a codimension-one linear space, so full-dimensionality of ΞGF implies that inequality (7) is facet-defining.This establishes the sufficiency direction of Theorem 6.
  • D.16 Proof of Lemma 5: Validity of the intersection inequality requires each pair to separate the endpoints of the other pair; otherwise a vertex subset produces a feasible vector violating the inequality.Assuming one pair is not a separator of the other yields a set containing v1,w1 but excluding v2,w2, with x_{v1w1}=0.
  • D.16 Proof of Lemma 5: Under mutual separator conditions, when both pair variables equal zero, a common connector and the edge {w1,w2} force both cross-pair variables to equal zero.Thus the intersection inequality holds in Case (a).
  • D.16 Proof of Lemma 5: When xv1w1 = 0 and xv2w2 = 1, connector augmentation forces at least one of xv2 and xw2 to equal 1, while the separator condition prevents both from equaling 1.This is the key connector argument for Case (b).

D.17 Proof of Theorem 7 … D.22 Proof of Proposition 9

The proofs establish facetness of the intersection inequality, transfer facet inequalities between the multi-separator and boolean quadric polytopes, and realize mutual projection relationships with lifted multicut polytopes. They also identify a path correspondence yielding total dual integrality.

  • D.17 Proof of Theorem 7: Under the stated separator assumptions, the intersection inequality (8) defines a facet of ΞGF.The proof constructs a basis for lin(X′ − X′), and full-dimensionality follows from Proposition 2.
  • D.18 Proof of Lemma 6: A valid inequality a(1 − x) ≤ α for ΞGF transfers to BQP(V,F) when coefficients outside E are nonnegative, and conversely when they are nonpositive.The constructions use z_v = 1 − x_v and z_uv = z_u z_v, with equality on graph edges.
  • D.18 Proof of Lemma 6: If the inequality is facet-defining for ΞGF and its nonzero coefficients lie in E, the corresponding inequality defines a facet of BQPG.The proof preserves the face dimension as |V| + |E| − 1 after removing zero-coefficient interaction coordinates.
  • D.19 Proof of Proposition 6: The lifted multicut polytope for G and G′ is the projection of a face of the multi-separator polytope Ξ b GF.The face fixes vertex components to zero and equates each e-component with its ve-component.
  • D.20 Proof of Proposition 7: Conversely, up to relabeling, ΞGF is the projection of a face of the lifted multicut polytope Γ ¯ G ¯ G′.The face fixes subdivision edges and imposes y_{v,¯v} + y_{v,ve} = 1, with x_v represented by y_{v,ve}.
  • D.21 Proof of Proposition 8: A multi-separator polytope for a path of length n corresponds one-to-one with the lifted multicut polytope for a path of length n + 1.The correspondence follows by renaming indices in the path and cut inequalities.
  • D.22 Proof of Proposition 9: The path formulation is totally dual integral because its systems correspond one-to-one with the totally dual integral system of Lange and Andres (2021).The conclusion follows directly from Theorem 1 of Lange and Andres (2021).
Loading 2608.16861v1…