求解最小红蓝分离集问题的优化技术及其在人类与人工智能文本区分中的应用

# Optimization Techniques for Solving the Minimum Red–Blue Separating Set Problem with an Application to Human–AI Text Separation
Source: [https://arxiv.org/html/2610.41081](https://arxiv.org/html/2610.41081)
Marko Djukanovi憆thanks:Corresponding author:marko\.dukanovic@ung\.siAffiliation:University of Nova Gorica, Nova Gorica, SloveniaAffiliation:Institute of Information Sciences \(IZUM\), Maribor, SloveniaStaša Vujičić Stankovi憆thanks:stasa\.vujicic\.stankovic@matf\.bg\.ac\.rsŽiga Zebec††thanks:ziga\.zebec@izum\.siAffiliation:Institute of Information Sciences \(IZUM\), Maribor, SloveniaChristian Blum††thanks:christian\.blum@csic\.esAffiliation:Artificial Intelligence Research Institute \(IIIA\-CSIC\), Barcelona, Spain

###### Abstract

We study the so\-called Minimum Red–Blue Separating Set Problem \(MRBSSP\) which arises from computational geometry\. In particular, we propose a compact Set\-Cover ILP formulation, safe preprocessing rules, a Greedy Randomized Adaptive Search Procedure \(GRASP\), and two exact approaches: one is based on Logic\-Based Benders Decomposition \(LBBD\) approach, and the second represents a novel Branch\-and\-Benders\-Cut \(BBC\) approach\. These two exact approaches are compared to ILP–alongside GRASP and the Variable Neighborhood Search \(VNS\) from literature\. Experiments on 250 random graphs with up to 500 vertices reveal complementary strengths: ILP yields the best feasible solutions, LBBD provides the strongest lower bounds and smallest mean optimality gap, and BBC certifies optimality most frequently\. We further introduce an NLP application distinguishing human\- and AI\-generated texts through vocabulary\-based graph features\. On 42 instances, BBC achieves the smallest mean optimality gap, certifying 16 optima, while GRASP outperforms VNS\. Structural analysis of optimal vocabulary separators identifies 113 mandatory and 151 replaceable features across 272 tests, highlighting substantial variability among optimal solutions\. Overall, our results demonstrate the effectiveness of complementary optimization strategies and the interpretability of optimal vocabulary\-based discrimination\.

## 1Introduction

Separating objects of different types by a small number of selected features, tests, or sensors is a recurring theme in combinatorial optimization, data analysis, and network design\[[4](https://arxiv.org/html/2610.41081#bib.bib4),[1](https://arxiv.org/html/2610.41081#bib.bib1),[2](https://arxiv.org/html/2610.41081#bib.bib2),[25](https://arxiv.org/html/2610.41081#bib.bib25),[26](https://arxiv.org/html/2610.41081#bib.bib26)\]\. In graph settings, this principle leads naturally to separation problems in which the goal is not merely to dominate or cover vertices, but to distinguish pairs of vertices belonging to different classes\. The Minimum Red\-Blue Separating Set Problem \(MRBSSP\) captures this requirement in a particularly compact form\. Given a graphG=\(V,E\)G=\(V,E\)and two disjoint sets of terminals, red verticesRRand blue verticesBB, the task is to select a minimum\-cardinality subsetS⊆VS\\subseteq Vsuch that every red\-blue pair\(r,b\)∈R×B\(r,b\)\\in R\\times Bis separated by at least one selected vertex\. A vertexv∈Vv\\in Vseparates the pair\(r,b\)\(r,b\)if its closed neighborhoodN⁡\[v\]N\[v\]contains exactly one ofrrandbb\. Thus, each selected vertex acts as a local test: it distinguishes precisely those terminal pairs for which one endpoint is inside its closed neighborhood and the other is outside\.

MRBSSP can be viewed as a structured Set\-Cover problem\[[7](https://arxiv.org/html/2610.41081#bib.bib7),[22](https://arxiv.org/html/2610.41081#bib.bib22),[10](https://arxiv.org/html/2610.41081#bib.bib10)\]\. The universe of elements to be covered is the Cartesian productR×BR\\times B, and each candidate vertexv∈Vv\\in Vcovers the subset of red\-blue pairs that it separates\. The natural integer programming formulation therefore contains one binary variable for each vertex and one covering constraint for each red\-blue terminal pair\. This formulation is conceptually simple and results in a direct exact model, but it can become large even for moderate instances, since the number of constraints grows with\|R\|​\|B\|\|R\|\|B\|\. Moreover, many of these constraints may be irrelevant for a large part of the search, because a candidate solution typically violates only a small subset of all red\-blue pairs\. This observation is the starting point for the decomposition and cut\-generation methods\[[32](https://arxiv.org/html/2610.41081#bib.bib32),[33](https://arxiv.org/html/2610.41081#bib.bib33)\]studied in this paper\.

The problem is closely related to several established lines of research\. At the most general level, MRBSSP inherits the modeling structure and computational difficulty of Set Cover and Hitting Set\[[35](https://arxiv.org/html/2610.41081#bib.bib35),[17](https://arxiv.org/html/2610.41081#bib.bib17)\], classical NP\-hard problems for which integer programming, greedy heuristics, and approximation algorithms form the standard methodological toolkit\[[14](https://arxiv.org/html/2610.41081#bib.bib14)\]\. It is also related to Red\-Blue Set Cover, introduced by Carr et al\.\[[8](https://arxiv.org/html/2610.41081#bib.bib8)\], where the objective is to cover all blue elements while minimizing the number of red elements covered\. Although MRBSSP has a different graph\-based separation semantics, both problems share the same red\-blue modeling philosophy: one must satisfy conditions involving one color class while controlling how the other color class is affected\. More directly, MRBSSP is connected to the Red\-Blue Separation problem on graphs studied by Dev et al\.\[[13](https://arxiv.org/html/2610.41081#bib.bib13)\], where a small set of vertices is selected so that every red\-blue pair is distinguished by the closed neighborhood of at least one selected vertex\. That work establishes the graph\-theoretic and complexity foundations of the problem, including hardness results and approximation guarantees for the general case\. Complementing this theoretical line, Milojković\[[28](https://arxiv.org/html/2610.41081#bib.bib28)\]recently proposed a Variable Neighborhood Search \(VNS\)\[[30](https://arxiv.org/html/2610.41081#bib.bib30)\]heuristic for the MRBSSP, showcasing that neighborhood\-based metaheuristics can provide competitive feasible solutions for graph instances\. The present paper builds on this emerging computational perspective by focusing on exact and hybrid methods, using the VNS method from the literature\[[28](https://arxiv.org/html/2610.41081#bib.bib28)\]and the newly introduced GRASP as strong heuristic reference baselines while emphasizing certification and dual\-bound progress\.

From an algorithmic perspective, MRBSSP is particularly well suited to decomposition\. Once a candidate setSSof selected vertices is fixed, assessing feasibility reduces to a simple set\-intersection test: for every red\-blue pair\(r,b\)\(r,b\), one verifies whetherSScontains at least one vertex that separates the pair\. If such a pair is not separated, the corresponding Set\-Cover constraint is violated and can be added as a cut\. This structure is a natural match for Logic\-Based Benders Decomposition \(LBBD\)\[[23](https://arxiv.org/html/2610.41081#bib.bib23)\], where a master problem proposes a candidate solution and a logical subproblem either verifies feasibility or returns violated constraints\. It is also a natural match for Branch\-and\-Benders\-Cut \(BBC\), where the same feasibility oracle is embedded inside a single branch\-and\-bound tree through lazy constraint generation\[[31](https://arxiv.org/html/2610.41081#bib.bib31)\], in the spirit of the combinatorial Benders cuts of Codato and Fischetti\[[12](https://arxiv.org/html/2610.41081#bib.bib12)\]\. The essential distinction is that iterative LBBD repeatedly solves a sequence of master problems, whereas BBC preserves the global search tree and injects cuts only when they are needed\.

The motivation for this study is therefore twofold\. First, the direct ILP model for MRBSSP is easy to state but may be inefficient because it builds the full\|R\|​\|B\|\|R\|\|B\|constraint family in advance\. Second, purely heuristic methods such as GRASP or VNS can rapidly produce good feasible solutions, but they do not provide the dual bounds nor the optimality certification\. This creates a natural methodological question: can the structure of MRBSSP be exploited to obtain exact methods that retain the certification strength of integer programming while avoiding unnecessary constraint generation and benefiting from high\-quality heuristic incumbents?

We investigate this question on two deliberately different benchmark families\. The first is a broadRandombenchmark composed of synthetically generated graphs with varying sizes and densities\. Its role is to stress the algorithms under controlled structural variation and to permit a systematic comparison of primal performance, dual\-bound progress, optimality gaps, certification rates, and heuristic stability\. The second is an NLP\-derived benchmark in which human\- and AI\-generated texts are represented through vocabulary\-incidence graphs\. In this family, the selected separator has a direct feature\-selection interpretation: a minimum set of vocabulary features is sought that distinguishes every human–AI text pair\. The NLP instances therefore complement the synthetic study with a real\-data setting in which both computational performance and the structure of the resulting optimal separators can be interpreted\. The two benchmark families serve different but complementary purposes\.

To the best of our knowledge, this work is among the earliest systematic exact computational studies of MRBSSP\. It establishes optimality certificates for benchmark instances previously treated primarily by heuristic methods and compares three complementary exact strategies against two metaheuristic baselines across both synthetic and real\-data benchmark families\. The main contributions are as follows\.

- •We present a unified exact\-optimization framework for MRBSSP based on the Set\-Cover interpretation of red–blue pair separation\.
- •We formulate and compare three exact strategies, which, to the best of our knowledge, are the first ones developed for MRBSSP: a GRASP\-warm\-started ILP, an iterative LBBD method, and a BBC implementation based on lazy separation cuts within a single branch\-and\-bound tree\.
- •We develop a GRASP construction and local\-improvement procedure used both as a standalone heuristic and as a source of high\-quality incumbents for the exact methods, and compare it with a VNS baseline from the literature\.
- •We show how MRBSSP feasibility can be checked by a simple logical oracle that detects uncovered red–blue pairs and generates valid Set\-Cover cuts, with only a limited number of heuristically selected cuts added per LBBD iteration or BBC callback invocation\.
- •We conduct a broad computational study on aRandombenchmark of 250 graphs spanning multiple sizes and densities\. This benchmark is used for systematic algorithmic stress testing, including primal quality, lower\-bound progress, optimality gaps, certification behavior, parameter tuning, and repeated\-run stability of GRASP and VNS\.
- •We introduce a second, structurally different benchmark family derived from NLP vocabulary\-separation instances for distinguishing human\- and AI\-generated texts, providing both a real\-data computational benchmark and an interpretable feature\-selection application of MRBSSP\. For the NLP benchmark, we go beyond objective\-value comparison and analyze the structure of certified optimal separators by forbidding selected vertices one at a time\. This distinguishes mandatory vocabulary features that occur in every optimum from replaceable features that belong only to some optimal solutions\.

### 1\.1Notation and Problem Restatement

LetG=\(V,E\)G=\(V,E\)be an undirected graph with disjoint vertex subsetsR⊆VR\\subseteq V\(red terminals\) andB⊆VB\\subseteq V\(blue terminals\),R∩B=∅R\\cap B=\\emptyset\. Forv∈Vv\\in V, letN⁡\[v\]=N⁡\(v\)∪\{v\}N\[v\]=N\(v\)\\cup\\\{v\\\}denote the closed neighborhood ofvv\. A vertexvv*separates*a red\-blue pair\(r,b\)∈R×B\(r,b\)\\in R\\times Bif

\|N⁡\[v\]∩\{r,b\}\|=1,\\bigl\|N\[v\]\\cap\\\{r,b\\\}\\bigr\|=1,i\.e\.,vv’s closed neighborhood contains exactly one of the two terminals\. For each pair\(r,b\)\(r,b\)define the*coverage set*

D⁡\(r,b\)=\{v∈V:\|N⁡\[v\]∩\{r,b\}\|=1\}\.D\(r,b\)\\;=\\;\\bigl\\\{\\,v\\in V\\;:\\;\|N\[v\]\\cap\\\{r,b\\\}\|=1\\,\\bigr\\\}\.A subsetS⊆VS\\subseteq Vis a*feasible red\-blue separator*if it intersectsD⁡\(r,b\)D\(r,b\)for every pair\(r,b\)∈R×B\(r,b\)\\in R\\times B, i\.e\.S∩D⁡\(r,b\)≠∅​∀\(r,b\)S\\cap D\(r,b\)\\neq\\emptyset\\ \\forall\(r,b\)\. The MRBSSP asks for a feasible separator of minimum cardinality:

MRBSSP:minS⊆V\|S\|s\.t\.S∩D\(r,b\)≠∅∀\(r,b\)∈R×B\.\\text\{MRBSSP:\}\\qquad\\min\_\{S\\subseteq V\}\\;\|S\|\\quad\\text\{s\.t\.\}\\quad S\\cap D\(r,b\)\\neq\\emptyset\\ \\ \\forall\(r,b\)\\in R\\times B\.This is structurally a Set\-Cover / Hitting Set problem in which the “elements to be covered” are the\|R\|×\|B\|\|R\|\\times\|B\|red\-blue pairs and the “sets” are the per\-vertex incidences induced byD⁡\(⋅,⋅\)D\(\\cdot,\\cdot\)\.

The remainder of the paper is organized as follows\. Sectionintroduces the classical Set\-Cover ILP formulation and the preprocessing rules used by the exact approaches\. Section[2](https://arxiv.org/html/2610.41081#S2)presents the GRASP heuristic and its role in providing validated warm starts and upper bounds\. Sections[3](https://arxiv.org/html/2610.41081#S3)and[4](https://arxiv.org/html/2610.41081#S4)present the LBBD and BBC algorithms, respectively\. Section[5](https://arxiv.org/html/2610.41081#S5)reports the first benchmark study on theRandomgraph family, including parameter tuning and comparisons of primal quality, lower\-bound strength, optimality gaps, certification behavior, and repeated\-run heuristic stability\. Section[6](https://arxiv.org/html/2610.41081#S6)presents the second benchmark family, derived from NLP vocabulary\-separation instances for distinguishing human\- and AI\-generated texts\. In addition to comparing all five approaches, it analyzes the structure of certified optimal vocabulary separators in terms of mandatory and replaceable features\. Section[7](https://arxiv.org/html/2610.41081#S7)concludes the paper by synthesizing the evidence from these two benchmark families and outlining algorithmic and application\-level directions for future work\.

### 1\.2Classical ILP \(Set\-Cover\) Formulation

Let define a binary decision variablexv∈\{0,1\}x\_\{v\}\\in\\\{0,1\\\}for everyv∈Vv\\in V, withxv=1x\_\{v\}=1if and only ifv∈Sv\\in S, whereSSdenotes a solution of the tackled problem\. The direct ILP formulationℳ\\mathcal\{M\}is given as follows:

min∑v∈Vxv\\displaystyle\\min\\quad\\sum\_\{v\\in V\}x\_\{v\}\(1\)s\.t\.∑v∈D⁡\(r,b\)xv≥1∀\(r,b\)∈R×B,\\displaystyle\\text\{s\.t\.\}\\quad\\sum\_\{v\\in D\(r,b\)\}x\_\{v\}\\;\\geq\\;1\\qquad\\forall\(r,b\)\\in R\\times B,\(2\)xv∈\{0,1\}∀v∈V\.\\displaystyle x\_\{v\}\\in\\\{0,1\\\}\\qquad\\forall v\\in V\.\(3\)Constraint family \([2](https://arxiv.org/html/2610.41081#S1.E2)\) is the bottleneck of this formulation: it contains\|R\|×\|B\|\|R\|\\times\|B\|rows, many of which are*never tight*at an optimal \(or even near\-optimal\) solution on sparse, large instances, yet all of them must be generated, stored, and processed by the presolver and the branch\-and\-cut engine before the first relaxation is even solved\. This motivates decomposing the model so that covering constraints are generated*only when violated*, which is exactly the role played by the Benders\-style methods of Sections[3](https://arxiv.org/html/2610.41081#S3)–[4](https://arxiv.org/html/2610.41081#S4)\.

Pre\-processing \(kernelization\) can shrink \([2](https://arxiv.org/html/2610.41081#S1.E2)\) before the model is passed to a solver\. A pair with\|D⁡\(r,b\)\|=1\|D\(r,b\)\|=1forces its unique covering vertex into every feasible solution \(an*essential*vertex\); rows whose coverage set is a strict superset of another row’s are dominated and can be dropped, representing therowdominance filtering\. This is implemented in the functionRowDominanceReduction\(\), returning non\-dominated set of constraints of the basic modelℳ\\mathcal\{M\}\. A vertex whose set of covered pairs is a strict subset of another surviving vertex’s coverage is called dominated and can be removed, representing thecolumndominance filtering\. This is implemented in the functionColumnDominanceReduction\(\), returning non\-dominated set of vertices that are kept from the basic modelℳ\\mathcal\{M\}\. These are the classical data reduction rules for set covering, whose effect on large real\-world instances was demonstrated by Weihe\[[36](https://arxiv.org/html/2610.41081#bib.bib36)\]\. The reductions are applied iteratively\. LetV\(k\)V^\{\(k\)\}denote the currently surviving vertex set andC\(k\)C^\{\(k\)\}the set of surviving constraints comprised of the variables from the setV\(k\)V^\{\(k\)\}, to keep the reduced instance internally consistent\. Formally, the column coverage is computed over surviving vertices, i\.e\.,C⁡\(v\)=\{\(r,b\):v∈D⁡\(r,b\)∩V\(k\)\}C\(v\)=\\\{\(r,b\):v\\in D\(r,b\)\\cap V^\{\(k\)\}\\\}, and after every column\-removal step each remaining separation set is explicitly synchronized with the current vertex set,

D⁡\(r,b\)←D⁡\(r,b\)∩V\(k\)\.D\(r,b\)\\leftarrow D\(r,b\)\\cap V^\{\(k\)\}\.\(4\)Thus a vertex removed in an earlier dominance round cannot remain as a stale element of a laterD⁡\(r,b\)D\(r,b\)set\. As a remark, in the implementation, the coverage loop therefore iterates overD⁡\(r,b\)∩V\(k\)D\(r,b\)\\cap V^\{\(k\)\}, not over the unreduced setD⁡\(r,b\)D\(r,b\)\.

Before any heuristic warm start is constructed, a full feasibility sanity check is performed\. If some red–blue pair hasD⁡\(r,b\)=∅D\(r,b\)=\\emptyset, the instance is declaredinfeasibleand GRASP, presented in Section[2](https://arxiv.org/html/2610.41081#S2)or any other effective procedure is not called\. For feasible instances, any approximate methodsℋ\\mathcal\{H\}may provide a MIP start and an objective cutoff\. The pseudocode of solving modelℳ\\mathcal\{M\}is presented in Algorithm[1](https://arxiv.org/html/2610.41081#alg1)\.

Algorithm 1Classical Set\-Cover ILP for MRBSSP with preprocessing and warm start1:Graph

G=\(V,E\)G=\(V,E\), terminal sets

R,BR,B, Heuristic procedure

ℋ\\mathcal\{H\}to generate approximate solutions

2:Optimal separator

S∗S^\{\\ast\}or infeasibility certificate

3:Compute

D⁡\(r,b\)D\(r,b\)for every

\(r,b\)∈R×B\(r,b\)\\in R\\times B
4:if

D⁡\(r,b\)=∅D\(r,b\)=\\emptysetfor some

\(r,b\)\(r,b\)then

5:returnInfeasible⊳\\trianglerightsanity check before GRASP

6:endif

7:

Ess←\{v:∃\(r,b\),D\(r,b\)=\{v\}\}Ess\\leftarrow\\\{v:\\exists\(r,b\),\\,D\(r,b\)=\\\{v\\\}\\\}⊳\\trianglerightessential vertices

8:

V\(k\)←V^\{\(k\)\}\\leftarrowColumnDominanceReduction\(

ℳ\\mathcal\{M\}\)

9:

C\(k\)←C^\{\(k\)\}\\leftarrowRowDominanceReduction\(

ℳ\\mathcal\{M\}\)

10:

D⁡\(r,b\)←D⁡\(r,b\)∩V\(k\)D\(r,b\)\\leftarrow D\(r,b\)\\cap V^\{\(k\)\}
11:

ℳ′←\(∑v∈V\(k\)xv,C\(k\),\{xv∈\{0,1\}:v∈V\(k\)\}\)\\mathcal\{M\}^\{\{\}^\{\\prime\}\}\\leftarrow\\left\(\\sum\_\{v\\in V^\{\(k\)\}\}x\_\{v\},C^\{\(k\)\},\\\{x\_\{v\}\\in\\\{0,1\\\}\\colon v\\in V^\{\(k\)\}\\\}\\right\)
12:

SH←S^\{\\text\{H\}\}\\leftarrowℋ\\mathcal\{H\}\(

G,R,BG,R,B\)⊳\\trianglerightRun an approximate method \(e\.g\., GRASP from Section[2](https://arxiv.org/html/2610.41081#S2)\)

13:

U​B←\|SH\|UB\\leftarrow\|S^\{\\text\{H\}\}\|; enable ILP start from

SHS^\{\\text\{H\}\}
14:Fix essential vertices in

ℳ′:includexv=1,v∈Ess\\mathcal\{M\}^\{\{\}^\{\\prime\}\}:\\text\{include \}x\_\{v\}=1,v\\in Ess,

∑vxv≤U​B\\sum\_\{v\}x\_\{v\}\\leq UB
15:

S∗←S^\{\\ast\}\\leftarrowSolve\(

ℳ′\\mathcal\{M\}^\{\{\}^\{\\prime\}\}\)⊳\\trianglerightPass the model to a solver

16:return

S∗S^\{\\ast\}

## 2GRASP Approach for the MRBSSP

The both designed exact approaches from Section[3](https://arxiv.org/html/2610.41081#S3)and Section[4](https://arxiv.org/html/2610.41081#S4)are seeded with an initial incumbent produced by a Greedy Randomized Adaptive Search Procedure \(GRASP\)\[[15](https://arxiv.org/html/2610.41081#bib.bib15)\]\. This section describes the GRASP approach, since its constructive and local\-search phases directly determine the quality of the warm start and, in turn, the upper\-bound cut \([9](https://arxiv.org/html/2610.41081#S4.E9)\) available to the exact methods\.

### 2\.1Overview

GRASP alternates between \(i\) a*randomized greedy construction*phase that builds a feasible separator from scratch, biased by a randomized restricted candidate list so that successive iterations explore different regions of the solution space, and \(ii\) a*local search*phase that greedily shrinks the constructed separator while preserving feasibility\. The best feasible separator found before the applicable stopping criterion is reached is returned asSGRASPS^\{\\text\{GRASP\}\}\. The resulting separator is supplied as a MIP start or used to define the upper\-bound cutoff \(see Eq\. \([9](https://arxiv.org/html/2610.41081#S4.E9)\) in Section[4](https://arxiv.org/html/2610.41081#S4)\)\.

During the execution time, GRASP repeatedly performs randomized greedy construction followed by local improvement and retains the best feasible separator encountered\. Pseudocode of the GRASP procedure is given in Algorithm[2](https://arxiv.org/html/2610.41081#alg2)\. Consequently, the GRASP solution actually supplied toBBCandLBBDas a warm start is*not*the same solution as the standaloneSGRASPS^\{\\text\{GRASP\}\}reported in the results table: the former results from only 10 iterations, whereas the latter is the best solution obtained during a 3600\-second search\. This distinction is essential for interpreting Section[5\.4](https://arxiv.org/html/2610.41081#S5.SS4)correctly and is revisited there\.

Algorithm 2GRASP for MRBSSP1:Graph

G=\(V,E\)G=\(V,E\), terminal sets

R,BR,B, candidate\-list size

lsize\>0l\_\{\\text\{size\}\}\>0
2:Heuristic separator

SGRASPS^\{\\text\{GRASP\}\}
3:

SGRASP←∅S^\{\\text\{GRASP\}\}\\leftarrow\\emptyset;

𝑐𝑜𝑠𝑡SGRASP←∞\\mathit\{cost\}^\{S^\{\\text\{GRASP\}\}\}\\leftarrow\\infty
4:whilestopping criterion has not been reacheddo

5:

S′←S^\{\{\}^\{\\prime\}\}\\leftarrowRandomizedGreedyConstruct\(

G,R,B,lsizeG,R,B,l\_\{\\text\{size\}\}\)⊳\\trianglerightSection[2\.2](https://arxiv.org/html/2610.41081#S2.SS2)

6:

S′←S^\{\{\}^\{\\prime\}\}\\leftarrowLocalSearch\(

G,R,B,S′G,R,B,S^\{\{\}^\{\\prime\}\}\)⊳\\trianglerightSection[2\.3](https://arxiv.org/html/2610.41081#S2.SS3)

7:if

\|S′\|<𝑐𝑜𝑠𝑡SGRASP\|S^\{\{\}^\{\\prime\}\}\|<\\mathit\{cost\}^\{S^\{\\text\{GRASP\}\}\}then

8:

SGRASP←S′S^\{\\text\{GRASP\}\}\\leftarrow S^\{\\prime\};

𝑐𝑜𝑠𝑡SGRASP←\|S′\|\\mathit\{cost\}^\{S^\{\\text\{GRASP\}\}\}\\leftarrow\|S^\{\\prime\}\|
9:endif

10:endwhile

11:return

SGRASPS^\{\\text\{GRASP\}\}

Unlike the exact methods of Sections[3](https://arxiv.org/html/2610.41081#S3)–[4](https://arxiv.org/html/2610.41081#S4), GRASP carries no optimality certificate: it returns a feasible separator and its size, but no lower bound\. Its role in this work is purely as a fast primal heuristic that \(a\) supplies a strong starting incumbent and \(b\) determines the right\-hand side of the upper\-bound cut \([9](https://arxiv.org/html/2610.41081#S4.E9)\) that tightens the BBC and LBBD master problems\.

### 2\.2Randomized Greedy Construction

The construction phase builds a separator one vertex at a time\. At each step it maintains the set of red\-blue pairs not yet separated by the partial solution and greedily selects a vertex that covers many of them, but—to allow GRASP’s iterations to diversify rather than collapse onto a single deterministic greedy solution—the selection is randomized among the top\-lsizel\_\{\\text\{size\}\}scoring candidates at each step \(a restricted candidate list of sizelsizel\_\{\\text\{size\}\}\) rather than always taking the single best\-scoring vertex\. The parameterlsizel\_\{\\text\{size\}\}controls the trade\-off between greedy quality \(smalllsizel\_\{\\text\{size\}\}, close to deterministic best\-first selection\) and diversification \(largerlsizel\_\{\\text\{size\}\}, more randomness across GRASP iterations\)\. The construction terminates once every pair inR×BR\\times Bis covered, which is guaranteed to occur in at most\|V\|\|V\|steps whenever the instance is separable\.

### 2\.3Local Search: 1\-Removal

The local\-search phase \(LS\) attempts to shrink the constructed separatorS′S^\{\\prime\}without ever leaving the feasible region\. It repeatedly scans the vertices currently in the solution and tests, for eachv∈Sv\\in S, whether removingvvleaves every pair still covered — equivalently, whethervvis not the*sole*remaining cover for any pair, i\.e\.,S∩D⁡\(r,b\)≠\{v\}S\\cap D\(r,b\)\\neq\\\{v\\\}for every\(r,b\)\(r,b\)\. The first vertex found to be removable is dropped, the covered\-pairs bookkeeping is updated incrementally, and the scan restarts on the reduced solution \(a first\-improvement, restart\-on\-success strategy\)\. The procedure terminates when a full scan finds no removable vertex, at which pointSSis*1\-removal\-minimal*: no single vertex can be deleted without uncovering some pair\. The pseudocode of the procedure is shown in Algorithm[3](https://arxiv.org/html/2610.41081#alg3)\.

Algorithm 3Local Search \(1\-Removal\) for MRBSSP1:Graph

G=\(V,E\)G=\(V,E\), terminal sets

R,BR,B, feasible separator

S′S^\{\\prime\}
2:1\-removal\-minimal feasible separator

SS
3:

S←S′S\\leftarrow S^\{\\prime\};

𝐶𝑜𝑣𝑒𝑟𝑒𝑑←\{\(r,b\):S∩D⁡\(r,b\)≠∅\}\\mathit\{Covered\}\\leftarrow\\\{\(r,b\):S\\cap D\(r,b\)\\neq\\emptyset\\\}
4:

𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑑←𝐭𝐫𝐮𝐞\\mathit\{improved\}\\leftarrow\\mathbf\{true\}
5:while

𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑑\\mathit\{improved\}do

6:

𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑑←𝐟𝐚𝐥𝐬𝐞\\mathit\{improved\}\\leftarrow\\mathbf\{false\}
7:foreach

v∈Sv\\in Sdo⊳\\trianglerightScan vertices in a fixed order

8:

𝐶𝑜𝑣𝑒𝑟𝑒𝑑′←𝐶𝑜𝑣𝑒𝑟𝑒𝑑∖\{\(r,b\):S∩D⁡\(r,b\)=\{v\}\}\\mathit\{Covered\}^\{\\prime\}\\leftarrow\\mathit\{Covered\}\\setminus\\\{\(r,b\):S\\cap D\(r,b\)=\\\{v\\\}\\\}⊳\\trianglerightpairs onlyvvcovers

9:if

𝐶𝑜𝑣𝑒𝑟𝑒𝑑′=R×B\\mathit\{Covered\}^\{\\prime\}=R\\times Bthen⊳\\trianglerightstill fully covered withoutvv

10:

S←S∖\{v\}S\\leftarrow S\\setminus\\\{v\\\};

𝐶𝑜𝑣𝑒𝑟𝑒𝑑←𝐶𝑜𝑣𝑒𝑟𝑒𝑑′\\mathit\{Covered\}\\leftarrow\\mathit\{Covered\}^\{\\prime\}
11:

𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑑←𝐭𝐫𝐮𝐞\\mathit\{improved\}\\leftarrow\\mathbf\{true\}
12:break⊳\\trianglerightrestart the scan on the reduced solution

13:endif

14:endfor

15:endwhile

16:return

SS

## 3Logic\-Based Benders Decomposition \(LBBD\): Core Methodological Approach

The central methodological idea of this work is to recognize that MRBSSP does not require all covering constraints \([2](https://arxiv.org/html/2610.41081#S1.E2)\) to be present explicitly in order to define a correct master problem\. A correct exact method requires only \(a\) a master problem that proposes candidate separators of minimum cardinality and \(b\) a procedure that can certify whether a candidate separator is feasible and, if not, explain*why*it is infeasible in a form that can be fed back to the master problem\. This is precisely the structure ofLogic\-Based Benders Decomposition\(LBBD\): classical Benders decomposition\[[6](https://arxiv.org/html/2610.41081#bib.bib6)\]derives cuts from LP duality applied to a continuous subproblem, whereas LBBD derives cuts from*logical inference*applied to a combinatorial feasibility subproblem\. For MRBSSP, this subproblem reduces to a simple set\-intersection test, which makes LBBD particularly well suited to this class of problems\.

##### Master Problem

The LBBD master problemℳLBBD\\mathcal\{M\}^\{\\text\{LBBD\}\}retains only the decision variables and the objective from the ILP of Section[1\.2](https://arxiv.org/html/2610.41081#S1.SS2)\. In its initial form, it contains the essential\-vertex fixing constraints but*no*red\-blue covering constraints:

min\\displaystyle\\min\\quad∑v∈Vndxv\\displaystyle\\sum\_\{v\\in V^\{\\text\{nd\}\}\}x\_\{v\}\(5\)s\.t\.xv=1∀v∈E​s​s\(essential vertices\)\\displaystyle x\_\{v\}=1\\qquad\\forall v\\in Ess\\quad\\text\{\(essential vertices\)\}\(6\)xv∈\{0,1\}∀v∈Vnd,\\displaystyle x\_\{v\}\\in\\\{0,1\\\}\\qquad\\forall v\\in V^\{\\text\{nd\}\},\(7\)
where the setVndV^\{\\text\{nd\}\}represents the set of non\-dominated candidate vertices obtained by applying row\- and column\-dominance reductions on the considered instance\. The resulting reduced separation coverage and surviving candidate vertices are then passed to the LBBD procedure\.

As shown in Algorithm[4](https://arxiv.org/html/2610.41081#alg4), the implementation may pass a GRASP separatorSGRASPS^\{\\text\{GRASP\}\}to the MIP solver at each master solve\. It is used as a MIP start and yields the valid cutoff∑v∈Vndxv≤\|SGRASP\|\\sum\_\{v\\in V^\{\\text\{nd\}\}\}x\_\{v\}\\leq\|S^\{\\text\{GRASP\}\}\|\(equivalently, after fixing the essential vertices,∑v∈Vnd∖E​s​sxv≤\|SGRASP\|−\|E​s​s\|\\sum\_\{v\\in V^\{\\text\{nd\}\}\\setminus Ess\}x\_\{v\}\\leq\|S^\{\\text\{GRASP\}\}\|\-\|Ess\|\)\.

At each iterationkk, solving the current relaxed master using this GRASP warm start yields a candidatex\(k\)x^\{\(k\)\}, which induces the candidate separatorS\(k\)=\{v:xv\(k\)=1,v∈Vnd\}S^\{\(k\)\}=\\\{v:x\_\{v\}^\{\(k\)\}=1,v\\in V^\{\\text\{nd\}\}\\\}\. Because only a limited number of covering constraints are present during the early iterations,S\(0\)S^\{\(0\)\}is typically the empty set \(or consists only of the essential vertices\) unless the solver accepts the supplied incumbent during the search\. The master objective value remains a valid*lower bound*on the true optimum at every iteration, since the master contains only valid constraints and a valid incumbent cutoff\.

##### Subproblem \(Logical Feasibility Oracle\)

Given a candidateS\(k\)S^\{\(k\)\}, the LBBD subproblem is*not*an LP, but rather a logical feasibility check:

Is​S\(k\)∩D⁡\(r,b\)≠∅for every​\(r,b\)∈R×B​?\\text\{Is \}S^\{\(k\)\}\\cap D\(r,b\)\\neq\\emptyset\\quad\\text\{for every \}\(r,b\)\\in R\\times B\\,?This test decomposes completely over pairs and can be evaluated for all pairs inO⁡\(\|R\|​\|B\|\)O\(\|R\|\|B\|\)time, given precomputed \(kernelized\)D⁡\(r,b\)D\(r,b\)sets\. These sets can themselves be computed once inO⁡\(\|R​‖B‖​V\|\)O\(\|R\|\|B\|\|V\|\)preprocessing time and reused across all iterations and all considered algorithms\. For a maximallyqLBBDq\_\{\\text\{LBBD\}\}pairs found to be*uncovered*byS\(k\)S^\{\(k\)\}, the logic\-based Benders feasibility cut

∑v∈D⁡\(r,b\)xv≥1\\sum\_\{v\\in D\(r,b\)\}x\_\{v\}\\;\\geq\\;1\(8\)is added into the master problemℳLBBD\\mathcal\{M\}^\{\\text\{LBBD\}\}\. These inequalities simply restate the necessary condition that the pair\(r,b\)\(r,b\)must be separated by at least one selected vertex\. Note that this feasibility cut is syntactically identical to the corresponding row \([2](https://arxiv.org/html/2610.41081#S1.E2)\) of the classical ILP\. The distinction is that LBBD generates such rows dynamically, only when they are violated by a master solution, rather than including the complete family of\|R\|​\|B\|\|R\|\|B\|constraints a priori\.

##### Controlled Multi\-Cut Strategy

At iterationkk, the oracle first identifies the complete set𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑\\mathit\{Violated\}of pairs not separated by the current candidate\. Instead of adding every corresponding row at once, the implementation selects a bounded subset𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑⊆𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑\\mathit\{Selected\}\\subseteq\\mathit\{Violated\}with\|𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑\|≤qLBBD\|\\mathit\{Selected\}\|\\leq q\_\{\\mathrm\{LBBD\}\}, whereqLBBDq\_\{\\mathrm\{LBBD\}\}is a user\-defined maximum number of cuts per iteration\. The default ranking prioritizes pairs with the smallest separation sets\|D⁡\(r,b\)\|\|D\(r,b\)\|, since these rows are typically more restrictive and cheaper to process\. WhenqLBBD=1q\_\{\\mathrm\{LBBD\}\}=1, the procedure reduces to a single\-cut scheme, whereas a sufficiently large value recovers the all\-cuts strategy\. This controlled multi\-cut policy prevents the first relaxed master solution from immediately generating the entire reduced ILP, while preserving exactness because at least one violated valid cut is appended whenever the current candidate is infeasible\.

Algorithm 4Iterative Logic\-Based Benders Decomposition for MRBSSP1:Graph

G=\(V,EG\)G=\(V,E\_\{G\}\), terminal sets

R,BR,B, cut limit

qLBBD≥1q\_\{\\mathrm\{LBBD\}\}\\geq 1,

lsize≥1l\_\{\\text\{size\}\}\\geq 1
2:Optimal separator

S∗S^\{\\ast\}or infeasibility certificate

3:Compute

D⁡\(r,b\)D\(r,b\)for every

\(r,b\)∈R×B\(r,b\)\\in R\\times B
4:if

D⁡\(r,b\)=∅D\(r,b\)=\\emptysetfor some pairthen

5:returnInfeasible

6:endif

7:Compute essential vertices; kernelize and compute non\-dominated constraints

CndC^\{\\text\{nd\}\}and vertices

VndV^\{\\text\{nd\}\}
8:Synchronize

D⁡\(r,b\)←D⁡\(r,b\)∩VndD\(r,b\)\\leftarrow D\(r,b\)\\cap V^\{\\text\{nd\}\}
9:

SGRASP←S^\{\\text\{GRASP\}\}\\leftarrowGRASP\(

G,R,B,lsizeG,R,B,l\_\{\\text\{size\}\}\)

10:Build the kernelized master

ℳ\\mathcal\{M\}and add its MIP start and cutoff

11:

k←0k\\leftarrow 0
12:repeat

13:

x\(k\)←x^\{\(k\)\}\\leftarrowSolve\(

ℳLBBD\\mathcal\{M\}^\{\\text\{LBBD\}\},

SGRASPS^\{\\text\{GRASP\}\}\)⊳\\trianglerightwarm start/cutoff, if available

14:

S\(k\)←\{v∈V:xv\(k\)=1\}S^\{\(k\)\}\\leftarrow\\\{v\\in V:x\_\{v\}^\{\(k\)\}=1\\\}
15:

𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑←\{\(r,b\)∈R×B:S\(k\)∩D⁡\(r,b\)=∅\}\\mathit\{Violated\}\\leftarrow\\bigl\\\{\\,\(r,b\)\\in R\\times B:S^\{\(k\)\}\\cap D\(r,b\)=\\emptyset\\,\\bigr\\\}
16:

𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑←\\mathit\{Selected\}\\leftarrowSelectCuts\(

𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑,qLBBD\\mathit\{Violated\},q\_\{\\mathrm\{LBBD\}\}\)⊳\\trianglerightat mostqLBBDq\_\{\\mathrm\{LBBD\}\}pairs; smallest\|D⁡\(r,b\)\|\|D\(r,b\)\|first

17:foreach

\(r,b\)∈𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑\(r,b\)\\in\\mathit\{Selected\}do

18:Add cut

∑v∈D⁡\(r,b\)xv≥1\\sum\_\{v\\in D\(r,b\)\}x\_\{v\}\\geq 1to

ℳLBBD\\mathcal\{M\}^\{\\text\{LBBD\}\}
19:endfor

20:

k←k\+1k\\leftarrow k\+1
21:until

𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑=∅\\mathit\{Violated\}=\\emptyset
22:

S∗←S\(k−1\)S^\{\\ast\}\\leftarrow S^\{\(k\-1\)\}
23:return

S∗S^\{\\ast\}

The complete LBBD procedure is shown in Algorithm[4](https://arxiv.org/html/2610.41081#alg4)\.

### 3\.1Correctness and Finite Termination

###### Proposition 1\.

Algorithm[4](https://arxiv.org/html/2610.41081#alg4)terminates after a finite number of iterations and returns an optimal solution to MRBSSP\.

###### Proof\.

\(Finite termination\.\)There are exactly\|R\|​\|B\|\|R\|\|B\|distinct pairs and, hence, at most\|R\|​\|B\|\|R\|\|B\|distinct cuts of the form \([8](https://arxiv.org/html/2610.41081#S3.E8)\) can ever be generated\. Each pair induces at most one distinct cut\. Even if a pair is violated again by a later candidate solution, its corresponding cut is generated at most once in an implementation that explicitly tracks previously added cuts\. SinceVVis finite, afterkkiterations the feasible region of the master problem is a subset of\{0,1\}\|V\|\\\{0,1\\\}^\{\|V\|\}intersected with at mostkkadditional linear inequalities\. Once all\|R\|​\|B\|\|R\|\|B\|possible cuts have been added in the worst case, the master becomes identical to the full ILP of Section[1\.2](https://arxiv.org/html/2610.41081#S1.SS2), and any optimal solution to it is directly feasible\. Therefore, the loop must terminate within at most\|R\|​\|B\|\+1\|R\|\|B\|\+1iterations\.

\(Optimality\.\)At every iterationkk,ℳLBBD\\mathcal\{M\}^\{\\text\{LBBD\}\}is a relaxation of the full ILP \([1](https://arxiv.org/html/2610.41081#S1.E1)\)–\([3](https://arxiv.org/html/2610.41081#S1.E3)\): it contains a strict subset of the covering constraints, together with the valid essential\-vertex fixing \([6](https://arxiv.org/html/2610.41081#S3.E6)\)\. Hence,z⁡\(ℳLBBD\)≤z∗z\(\\mathcal\{M\}^\{\\text\{LBBD\}\}\)\\leq z^\{\\ast\}for everykk, wherez∗z^\{\\ast\}is the true MRBSSP optimum andz⁡\(ℳLBBD\)z\(\\mathcal\{M\}^\{\\text\{LBBD\}\}\)is the optimal value of the master problem at iterationkk, and therefore a valid lower bound\. The loop terminates only whenS\(k\)S^\{\(k\)\}satisfies*every*covering constraint \([2](https://arxiv.org/html/2610.41081#S1.E2)\), i\.e\.,𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑=∅\\mathit\{Violated\}=\\emptyset\. This means thatS\(k\)S^\{\(k\)\}is feasible for the full ILP and, therefore,\|S\(k\)\|≥z∗\|S^\{\(k\)\}\|\\geq z^\{\\ast\}\. Combined withz⁡\(ℳLBBD\)=\|S\(k\)\|≤z∗z\(\\mathcal\{M\}^\{\\text\{LBBD\}\}\)=\|S^\{\(k\)\}\|\\leq z^\{\\ast\}, sinceS\(k\)S^\{\(k\)\}is the master’s own optimal solution at that iteration, we obtain\|S\(k\)\|=z∗\|S^\{\(k\)\}\|=z^\{\\ast\}, i\.e\.,S\(k\)S^\{\(k\)\}is optimal\. ∎

This argument is the logic\-based analogue of the classical Benders feasibility\-cut argument: instead of a dual certificate proving that a continuous subproblem is infeasible or suboptimal, the certificate here is the combinatorial factS\(k\)∩D⁡\(r,b\)=∅S^\{\(k\)\}\\cap D\(r,b\)=\\emptyset, which logically implies the cut\.

##### Limitation of the Iterative Scheme

Algorithm[4](https://arxiv.org/html/2610.41081#alg4)re\-solves the master MIP*from scratch*at every iteration \(the callSolve\(ℳ,SGRASP\)\(\\mathcal\{M\},S^\{\\text\{GRASP\}\}\)\. Although the GRASP warm start and cutoff are re\-applied at each solve, the branch\-and\-bound tree explored in the previous iteration is discarded after each new batch of cuts is appended\. On instances requiring many iterations, this repeated restart overhead can dominate the total running time, motivating the tighter integration described in the next section\.

## 4Branch\-and\-Benders\-Cut \(BBC\)

Branch\-and\-Benders\-Cut eliminates the restart overhead of Algorithm[4](https://arxiv.org/html/2610.41081#alg4)by embedding the same logical feasibility oracle directly within a*single*branch\-and\-bound search tree through alazy constraint callback\. Rather than solving the master to full MIP optimality, identifying violations, and re\-solving it, BBC intercepts the search when an integer\-feasible candidate is found, checks it immediately, and either accepts it or injects the missing cuts into the*same*tree before the search continues\. The pseudocode of BBC is shown in Algorithm[5](https://arxiv.org/html/2610.41081#alg5)\.

##### Master/Callback Architecture

The BBC master problem is identical in structure to the LBBD master \(Equations \([5](https://arxiv.org/html/2610.41081#S3.E5)\)–\([7](https://arxiv.org/html/2610.41081#S3.E7)\)\)\. The algorithm first checks whether any red–blue pair has an empty separation set; if so, it terminates with an infeasibility certificate\. Otherwise, it runs GRASP, and the resulting solution is used as a MIP start and to define the valid upper\-bound cutoff

∑v∈Vnd∖E​s​sxv≤\|SGRASP\|−\|E​s​s\|\.\\sum\_\{v\\in V^\{\\text\{nd\}\}\\setminus Ess\}x\_\{v\}\\;\\leq\\;\|S^\{\\text\{GRASP\}\}\|\-\|Ess\|\.\(9\)
The master is solved*once*, but the branch\-and\-bound engine invokes theFeasibilityOraclecallback \(see Algorithm[6](https://arxiv.org/html/2610.41081#alg6)\) whenever it discovers a new integer\-feasible candidate solution,*before*that candidate is accepted as the incumbent\. At each callback invocation, the oracle adds at mostqBBCq\_\{\\mathrm\{BBC\}\}lazy constraints rather than all currently violated rows\. The implemented ranking prioritizes pairs with the smallest\|D⁡\(r,b\)\|\|D\(r,b\)\|\. Since even a single violated lazy constraint excludes the current candidate, this policy remains exact while avoiding the immediate reconstruction of the complete reduced ILP at the first callback\.

Algorithm 5Branch\-and\-Benders\-Cut for MRBSSP — Master Driver1:Graph

G=\(V,E\)G=\(V,E\), terminal sets

R,BR,B, cut limit

qBBC≥1q\_\{\\mathrm\{BBC\}\}\\geq 1,

lsize≥1l\_\{\\text\{size\}\}\\geq 1
2:Optimal separator

S∗S^\{\\ast\}or infeasibility certificate

3:Compute

D⁡\(r,b\)D\(r,b\)for every

\(r,b\)∈R×B\(r,b\)\\in R\\times B
4:if

D⁡\(r,b\)=∅D\(r,b\)=\\emptysetfor some pairthen

5:returnInfeasible

6:endif

7:

SGRASP←S^\{\\text\{GRASP\}\}\\leftarrowGRASP\(

G,R,B,lsizeG,R,B,l\_\{\\text\{size\}\}\)

8:Compute essential vertices; kernelize and synchronize

D⁡\(r,b\)←D⁡\(r,b\)∩VndD\(r,b\)\\leftarrow D\(r,b\)\\cap V^\{\\text\{nd\}\}
9:Build master

ℳ\\mathcal\{M\}with objective \([5](https://arxiv.org/html/2610.41081#S3.E5)\), kernelization, and essential nodes

10:Add cutoff \([9](https://arxiv.org/html/2610.41081#S4.E9)\) and register the MIP start from

SGRASPS^\{\\text\{GRASP\}\}
11:Register callback

FeasibilityOracle​\(qBBC\)\\textsc\{FeasibilityOracle\}\(q\_\{\\mathrm\{BBC\}\}\)to be invoked for every integer\-feasible candidate

12:

S∗←S^\{\\ast\}\\leftarrowBranchAndBound\(

ℳ\\mathcal\{M\},

SGRASPS^\{\\text\{GRASP\}\}\)⊳\\trianglerightsingle search tree; never restarted

13:return

S∗S^\{\\ast\}

Whenever the solver encounters an integer\-feasible master candidate, the callback reconstructs the complete candidate separator, including all essential vertices fixed to 1 during preprocessing\. Thus,

S\(k\)=E​s​s∪\{v∈Vnd∖E​s​s:xv\(k\)=1\}\.S^\{\(k\)\}=Ess\\cup\\\{v\\in V^\{\\text\{nd\}\}\\setminus Ess:x\_\{v\}^\{\(k\)\}=1\\\}\.The feasibility oracle then checks this complete separator against all surviving red–blue separation requirements\.

Algorithm 6FeasibilityOracle— Lazy Constraint Callback1:Current integer\-feasible candidate values

x\(k\)x^\{\(k\)\}at a search node; essential\-vertex set

E​s​sEss; cut limit

qBBCq\_\{\\mathrm\{BBC\}\}
2:

S\(k\)←E​s​s∪\{v∈Vnd∖E​s​s:xv\(k\)=1\}S^\{\(k\)\}\\leftarrow Ess\\cup\\\{v\\in V^\{\\text\{nd\}\}\\setminus Ess:x\_\{v\}^\{\(k\)\}=1\\\}
3:

𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑←\{\(r,b\)∈R×B:S\(k\)∩D⁡\(r,b\)=∅\}\\mathit\{Violated\}\\leftarrow\\bigl\\\{\(r,b\)\\in R\\times B:S^\{\(k\)\}\\cap D\(r,b\)=\\emptyset\\bigr\\\}
4:if

𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑=∅\\mathit\{Violated\}=\\emptysetthen

5:accept

x\(k\)x^\{\(k\)\}as a valid incumbent⊳\\trianglerightno lazy constraint is required

6:else

7:

𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑←\\mathit\{Selected\}\\leftarrowSelectCuts\(

𝑉𝑖𝑜𝑙𝑎𝑡𝑒𝑑,qBBC\\mathit\{Violated\},q\_\{\\mathrm\{BBC\}\}\)⊳\\trianglerightat mostqBBCq\_\{\\mathrm\{BBC\}\}pairs; smallest\|D⁡\(r,b\)\|\|D\(r,b\)\|first

8:foreach

\(r,b\)∈𝑆𝑒𝑙𝑒𝑐𝑡𝑒𝑑\(r,b\)\\in\\mathit\{Selected\}do

9:Add lazy feasibility cut

∑v∈D⁡\(r,b\)xv≥1\\sum\_\{v\\in D\(r,b\)\}x\_\{v\}\\geq 1to the active search tree

10:endfor⊳\\trianglerightThe current candidate violates the newly added cut\(s\) and is rejected by the solver\.

11:endif

##### Why BBC Preserves the Search Tree

The crucial structural difference from Algorithm[4](https://arxiv.org/html/2610.41081#alg4)is thatFeasibilityOracledoes not stop or restart the branch\-and\-bound process; instead, it is invoked*synchronously*within the solver’s incumbent\-acceptance routine\. Adding a cut violated by the current candidate is sufficient for the solver to treat that candidate as infeasible\. The search then continues within the same branch\-and\-bound tree, with the newly added valid inequalities remaining active throughout the remainder of the search and being inherited by all subsequently explored nodes, including siblings and descendants of already processed nodes that may benefit from the new cut through bound tightening\. This is precisely what eliminates the restart overhead identified as the limitation of Section[3](https://arxiv.org/html/2610.41081#S3): LBBD restarts the branch\-and\-bound search after each new batch of cuts, whereas BBC maintains a single search tree throughout\.

### 4\.1Correctness

###### Theorem 1\.

Algorithm[5](https://arxiv.org/html/2610.41081#alg5)\(with callback[6](https://arxiv.org/html/2610.41081#alg6)\) terminates and returns an optimal solution to MRBSSP\.

###### Proof\.

Branch\-and\-bound over the finite domain\{0,1\}\|V∖E\|\\\{0,1\\\}^\{\|V\\setminus E\|\}terminates in finite time regardless of how many lazy cuts are injected during the search, since each cut only*removes*candidate solutions and the underlying search tree remains finite\. This is a standard property of lazy\-constraint branch\-and\-cut: although at mostqBBCq\_\{\\mathrm\{BBC\}\}cuts are added per callback invocation, every infeasible integer candidate triggers at least one valid cut\. The lazy\-constraint pool therefore grows monotonically and is bounded above by\|R\|​\|B\|\|R\|\|B\|distinct rows, exactly as argued in Proposition[1](https://arxiv.org/html/2610.41081#Thmproposition1)\.

For optimality, observe that the solver reports an incumbentx∗x^\{\\ast\}as final only if \(a\) it is provably optimal with respect to every constraint currently present in the model and \(b\)FeasibilityOraclefinds no violated pair for it\. Otherwise, a new cut would be added andx∗x^\{\\ast\}would be excluded by that cut, contradicting \(a\)\. Condition \(b\) means thatS∗=\{v:xv∗=1\}S^\{\\ast\}=\\\{v:x^\{\\ast\}\_\{v\}=1\\\}satisfiesS∗∩D⁡\(r,b\)≠∅S^\{\\ast\}\\cap D\(r,b\)\\neq\\emptysetfor*every*\(r,b\)∈R×B\(r,b\)\\in R\\times B\. Thus,S∗S^\{\\ast\}is feasible for the full ILP \([1](https://arxiv.org/html/2610.41081#S1.E1)\)–\([3](https://arxiv.org/html/2610.41081#S1.E3)\), and therefore\|S∗\|≥z∗\|S^\{\\ast\}\|\\geq z^\{\\ast\}\. Conversely, every cut that is added is a logically valid inequality \(Equation \([8](https://arxiv.org/html/2610.41081#S3.E8)\) restates a necessary condition for feasibility\), so the relaxed model solved at termination remains a valid relaxation of the full ILP, yielding\|S∗\|≤z∗\|S^\{\\ast\}\|\\leq z^\{\\ast\}by the same relaxation argument used in Proposition[1](https://arxiv.org/html/2610.41081#Thmproposition1)\. Hence,\|S∗\|=z∗\|S^\{\\ast\}\|=z^\{\\ast\}\. ∎

###### Corollary 1\.

LBBD \(Algorithm[4](https://arxiv.org/html/2610.41081#alg4)\) and BBC \(Algorithm[5](https://arxiv.org/html/2610.41081#alg5)\) are equivalent in terms of the cut family they may generate: both are restricted to the same universe of at most\|R\|​\|B\|\|R\|\|B\|valid inequalities \([8](https://arxiv.org/html/2610.41081#S3.E8)\) and therefore solve to the same optimal objective valuez∗z^\{\\ast\}on any instance\. They differ only in*when*and*how*those cuts are discovered and exploited during the search, which affects running time and the number of explicitly materialized constraints, but not solution quality or correctness\.

### 4\.2Discussion: Why BBC Is a Natural Fit for MRBSSP

Three structural properties of MRBSSP jointly make it a favorable candidate for the Logic\-Based Branch\-and\-Benders\-Cut paradigm, in contrast to problems whose Benders subproblems are themselves expensive LPs:

1. 1\.A compact master\.The master retains only\|V\|\|V\|binary variables and the simple essential\-vertex fixing constraints \([6](https://arxiv.org/html/2610.41081#S3.E6)\); it contains none of the\|R\|​\|B\|\|R\|\|B\|structural rows\.
2. 2\.A cheap feasibility oracle\.CheckingS\(k\)∩D⁡\(r,b\)≠∅S^\{\(k\)\}\\cap D\(r,b\)\\neq\\emptysetfor all pairs requires only a simple set\-intersection sweep,O⁡\(\|R\|​\|B\|\)O\(\|R\|\|B\|\)given precomputed coverage sets, with no LP or combinatorial subproblem to solve\.
3. 3\.Simple, sparse, valid cuts\.Each generated cut is a single≥1\\geq 1row overD⁡\(r,b\)D\(r,b\), syntactically identical to a row of the original ILP and requiring no auxiliary variables or big\-MMconstants\.

Combining this structure with safe iterative kernelization \(essential vertices and row/column dominance with synchronization of the surviving separation sets\) and a feasibility\-validated GRASP warm start substantially reduces the number of explicitly materialized constraints while still exploiting the solver’s native branch\-and\-cut engine\. When GRASP is feasible, it supplies both an initial incumbent and the upper\-bound cut \([9](https://arxiv.org/html/2610.41081#S4.E9)\); otherwise, both are omitted without affecting exactness\.

## 5Experimental Results

TheRandombenchmark contains 250 instances arranged in 25\(n,p\)\(n,p\)groups, wherennandpprepresent the graph size and the graph density, respectively, with 10 instances generated for each combination ofn∈\{20,50,100,200,500\}n\\in\\\{20,50,100,200,500\\\}andp∈\{0\.01,0\.05,0\.1,0\.2,0\.5\}p\\in\\\{0\.01,0\.05,0\.1,0\.2,0\.5\\\}\. Note that five sparse groups,\(20,0\.05\)\(20,0\.05\),\(20,0\.1\)\(20,0\.1\),\(50,0\.01\)\(50,0\.01\),\(100,0\.01\)\(100,0\.01\), and\(200,0\.01\)\(200,0\.01\), are identified as infeasible by the common feasibility checks involved in each of the exact approaches\. Therefore, the results on those instances are not reported here\. Thus, the quantitative comparison is reported for 200 feasible instances, i\.e\., 20 groups\.

Five approaches are evaluated: \(ii\) the compact ILP with theℋ\\mathcal\{H\}=GRASP warm start \(Ilp\); \(i​iii\) Branch\-and\-Benders\-Cut with the GRASP warm start \(Bbc\); \(i​i​iiii\) Logic\-based Benders decomposition with GRASP warm start \(Lbbd\); \(i​viv\) Standalone \(long\-run\)GRASPapproach \(Grasp\); \(vv\)VNSbaseline from the literature \(Vns\)\.

All algorithms are implemented in Python 3\.11, with the exact optimization models implemented using DOcplex and solved with IBM ILOG CPLEX 22\.1\. The experiments were conducted on the VEGA high\-performance computing system hosted at IZUM, Maribor\. The cluster comprises 960 compute nodes equipped with AMD EPYC 7H12 processors operating at 2\.35 GHz\. To ensure a consistent computational setting across all tested approaches, all experiments were executed in single\-threaded mode\.

Each exact method was given a 3600\-second time limit after preprocessing and warm\-start generation\. On theRandominstances these pre\-solve phases take from several milliseconds to a few hundred seconds\. On the NLP instances they take considerably longer: according to the LBBD logs, 123 to 158 s for𝑞𝑛𝑠=100\\mathit\{qns\}=100, 482 to 881 s for𝑞𝑛𝑠=150\\mathit\{qns\}=150, 1752 to 3979 s for𝑞𝑛𝑠=200\\mathit\{qns\}=200and 4274 to 6563 s for𝑞𝑛𝑠=250\\mathit\{qns\}=250\. The time limits reported for the exact methods therefore refer to the solver phase only\. The stochastic heuristic approaches were run independently ten times on each feasible instance, with every standalone \(long\-run\)GraspandVnsrun subject to a 3600\-second wall\-clock limit\. ForGrasp, the solution reported for a run is the best feasible separator obtained before the time limit is reached\. The substantially cheaper 10\-iterationGraspis used for the warm\-start, to initialize the exact methods as a separate procedure\. The bothGraspsettings utilized the size of restricted listlsizel\_\{\\text\{size\}\}to 5, selected after several preliminary results\. For each heuristic, the ten runs are first averaged within an instance and only then aggregated by\(n,p\)\(n,p\), so every graph receives equal statistical weight\.

### 5\.1Algorithm tuning

BbcandLbbdeach expose one strategically important algorithm\-specific parameter\. We denote byqBBCq\_\{\\mathrm\{BBC\}\}the maximum number of violated separation constraints added during oneBbccallback and byqLBBDq\_\{\\mathrm\{LBBD\}\}the maximum number added during oneLbbdmaster iteration\. The parameter controls a natural trade\-off\. Small values keep each generated cut batch selective but may require many callbacks or repeated master solves, whereas very large values reduce the number of separation rounds at the price of substantially enlarging the current relaxation or master problem\.

We tune these parameters on dedicated subsets of both theRandomand NLP benchmarks before fixing the values used in the final experiments\. The tested values are

qLBBD,qBBC∈\{1,2,5,10,50,100,500\}\.q\_\{\\mathrm\{LBBD\}\},q\_\{\\mathrm\{BBC\}\}\\in\\\{1,2,5,10,50,100,500\\\}\.Parameter selection is based primarily on the final optimality gap and the number of proven optima; primal and dual bound quality and the number of separation rounds are used as secondary diagnostics\.

#### 5\.1\.1Tuning on theRandombenchmark

The completedRandomtuning study evaluates the full parameter grid for bothBbcandLbbd\. The tuning set contains 20 instances, selecting one instance at random from each group of theRandombenchmark\. The aggregated results are reported in Appendix[A](https://arxiv.org/html/2610.41081#A1)\.

The completedBbcexperiment confirmsqBBC=5q\_\{\\mathrm\{BBC\}\}=5as theRandom\-specific choice\. It yields the smallest mean gap \(25\.39%\) and is the only tested value proving 10 of the 20 tuning instances optimal\. TheqBBC=500q\_\{\\textrm\{BBC\}\}=500run gives mean gap 26\.16% and 9 optimality certificates\. Thus, increasing the callback batch from 5 to 500 reduces the average number of callbacks from 241\.45 to 46\.75, but increases the number of lazy rows materialized and does not improve final certificate quality\. This confirms thatBbcbenefits from a relatively selective cut batch inside one branch\-and\-bound tree\.

ForLbbd,qLBBD=100q\_\{\\mathrm\{LBBD\}\}=100remains the strongestRandom\-specific value, with mean gap 24\.85% and 9 proven optima\. AtqLBBD=500q\_\{\\mathrm\{LBBD\}\}=500, the number of master iterations falls further from 10\.35 to 5\.30, but the mean gap worsens to 25\.86% and the number of certificates falls to 8\. Hence the completeRandomtuning grid shows a clear over\-batching regime beyondqLBBD=100q\_\{\\mathrm\{LBBD\}\}=100forLbbd\.

![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/tuning_random_gap.png)Figure 1:Mean optimality gap on the completeRandomtuning grid across differentq=qLBBD,qBBCq=q\_\{\\text\{LBBD\}\},q\_\{\\text\{BBC\}\}values\.
![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/tuning_random_lbbd_iterations.png)Figure 2:Mean number of LBBD master iterations on theRandombenchmark as the maximum number of cuts per iteration increases\.

The completed benchmark\-specific tuning therefore selects

\(qBBC,qLBBD\)=\(5,100\)​forRandom\.\(q\_\{\\mathrm\{BBC\}\},q\_\{\\mathrm\{LBBD\}\}\)=\(5,100\)\\text\{ for \{Random\}\}\.

### 5\.2Overall exact\-method behavior

After tuning,Bbcis run withqBBC=5q\_\{\\mathrm\{BBC\}\}=5andLbbdwithqLBBD=100q\_\{\\mathrm\{LBBD\}\}=100on the completeRandombenchmark\.Vnsuses the settings from\[[28](https://arxiv.org/html/2610.41081#bib.bib28)\], andGrasputilizes the same configuration reported in Section[2](https://arxiv.org/html/2610.41081#S2)\. All three exact methods use the same 10\-iterationGraspwarm\-start procedure; otherwise,Ilpuses CPLEX’s default settings\. Table[1](https://arxiv.org/html/2610.41081#S5.T1)summarizes the resulting exact\-method performance on all 200 feasible instances\.

Table 1:Overall results of the exact methods on the 200 \(feasible\)Randominstances after tuning\.Ilpremains the strongest exact method on the primal side, with mean UB 18\.83\. TunedLbbdgives the strongest mean lower bound \(13\.63\) and the smallest mean gap \(24\.37%\), while tunedBbcproves the largest number of instances solved to optimality \(92/200\)\. Instance\-wise,Ilpattains a best or tied\-best exact UB on 191 instances and is uniquely best on 38;BbcandLbbdare uniquely best on 3 and 2 instances, respectively\. On the dual side,Lbbdis uniquely best on 80 instances, compared with 1 forBbcand 0 forIlp\.

### 5\.3Optimality gap and lower\-bound quality

Over the 200 paired feasible instances, a Friedman test detects a significant difference among the exact\-method gaps \(χ2=124\.03\\chi^\{2\}=124\.03,p<10−12p<10^\{\-12\}\)\. The aggregate mean gaps are 29\.54% forIlp, 25\.97% forBbc, and 24\.37% forLbbd\. On the 11 groups for which at least one exact method does not solve all ten instances, the mean group gaps are 53\.71%, 47\.21%, and 44\.30%, respectively\.

![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/random_posttuning_gap.png)Figure 3:Mean optimality gaps ofIlp, tunedBbc, and tunedLbbdon the feasibleRandomgroups\.Table 2:Mean lower bounds after tuning\. Bold indicates the strongest mean lower bound in each group\.Using⌈LB⌉=UB\\lceil\\mathrm\{LB\}\\rceil=\\mathrm\{UB\}as the certification criterion,Bbcproves 92 of the 200 feasible instances optimal, compared with 90 forIlpand 91 forLbbd\.

### 5\.4Primal solution quality: exact methods and meta\-heuristics

GraspandVnsachieve overall mean solution sizes of 19\.65 and 19\.52, respectively, and on the largest instances they frequently provide better primal solutions than the incumbents returned by the exact methods within the time limit\. On the 200 paired feasible instances,Graspis better on 57,Vnson 40, and the methods tie on 103; the paired Wilcoxon test remains non\-significant \(p=0\.414p=0\.414\)\. Relative to the best exact incumbent after tuning, the mean excess is 0\.81% forGraspand 1\.41% forVns\. All numerical results are shown in Table[3](https://arxiv.org/html/2610.41081#S5.T3)\.

Table 3:Mean upper bounds after tuning\. Bold indicates the smallest value in each group\.We note that the mean within\-instance standard deviations of the two heuristic approaches remain 0\.21 forGraspand 0\.22 forVns\.

The post\-tuningRandomresults therefore sharpen the division of roles:Ilpis the strongest primal exact method,Lbbdgives the strongest dual bounds and smallest mean gap, andBbcproves the largest number of instances optimal\.

## 6NLP Benchmark: Vocabulary Separation for Human\- and AI\-Generated Text

### 6\.1Motivation and graph interpretation

The NLP benchmark investigates a feature\-selection interpretation of MRBSSP in which red and blue vertices represent texts from two classes \(human\-generated and AI\-generated\), while neutral vertices represent candidate vocabulary features\. The objective is to identify a smallest set of vocabulary features whose graph\-incidence patterns distinguish every red–blue pair\. The separator here is forced to rely on neutral vocabulary features\.

##### Relation to work on machine\-generated text\.

Detection of machine\-generated text is an active research area; a recent survey is given by Wu et al\.\[[37](https://arxiv.org/html/2610.41081#bib.bib37)\]\. Many detectors assign a score to a document, either through a trained classifier or through statistics of token probabilities under a language model\[[18](https://arxiv.org/html/2610.41081#bib.bib18),[29](https://arxiv.org/html/2610.41081#bib.bib29)\], and their decisions are not stated in terms of a small set of observable features; detectors that do rely on a small set of stylometric or lexical features do not ask whether that set is the smallest one that separates the sample\. Studies that compare human\-written and machine\-generated texts directly report systematic differences in vocabulary and style\. Herbold et al\.\[[21](https://arxiv.org/html/2610.41081#bib.bib21)\]compare essays written by students and by ChatGPT with respect to lexical diversity, syntactic complexity and the use of modal, epistemic and discourse markers, and Kobak et al\.\[[24](https://arxiv.org/html/2610.41081#bib.bib24)\]identify words whose frequency in biomedical abstracts increased sharply after large language models became widely available\. In both cases the differences are established by frequency statistics over large collections of texts\. In text classification, feature selection methods rank words by criteria such as document frequency, theχ2\\chi^\{2\}statistic or information gain\[[38](https://arxiv.org/html/2610.41081#bib.bib38),[16](https://arxiv.org/html/2610.41081#bib.bib16)\], and the number of retained words is left to the user\. The MRBSSP formulation asks a different question: what is the smallest set of words whose presence or absence distinguishes every human\-written text of a given sample from every machine\-generated text of the same sample? In rough set theory this object is a minimum decision re\-duct of the binary decision table whose objects are the texts, whose attributes are the candidate words and whose decision is the class\[[34](https://arxiv.org/html/2610.41081#bib.bib34)\], and the exact methods of this paper make it possible to certify that no smaller set exists\. The benchmark is not intended as a new detector\. Separating all pairs of a fixed sample is a property of that sample, and the classification of unseen texts is not evaluated here\. In practice, a certified minimum separator is a tool for inspecting a data set rather than for labelling new texts\. Its size is a lower bound on the number of words that any rule based on word presence needs in order to tell the two sources apart on that sample, so it measures how far apart the two sources are lexically and can be compared across samples, domains or generators\. Its content shows which words suffice for the separation; when these are a few function words or topic words, as in Section[6\.7](https://arxiv.org/html/2610.41081#S6.SS7), a detector trained on the same sample can separate it perfectly through surface features unrelated to authorship, which is the kind of shortcut that benchmark construction for machine\-text detection tries to avoid\.

##### Corpus and sampling\.

The instances are built from the English part of the HC3 corpus \(Human ChatGPT Comparison Corpus\)\[[20](https://arxiv.org/html/2610.41081#bib.bib20)\]\. HC3 contains 24 322 questions from five sources \(Reddit ELI5, finance, medicine, open\-domain question answering and Wikipedia\-based computer science\), together with 58 546 human\-written answers and 26 903 answers generated by ChatGPT\. Every question has at least one human answer; most questions have one ChatGPT answer, 1 833 have several and 455 have none\. An instance is determined by the number𝑞𝑛𝑠\\mathit\{qns\}of questions and by a seed\. The𝑞𝑛𝑠\\mathit\{qns\}questions are drawn uniformly at random without replacement from the whole corpus, using a pseudo\-random number generator initialized with the seed, and for every drawn question the first human answer and all ChatGPT answers are retained\. The seeds are the consecutive integers 42 to 51 and were fixed before any experiment was run, so that no sample was selected or discarded on the basis of the results\. Since the generator draws the questions one at a time, the sample of𝑞𝑛𝑠\\mathit\{qns\}questions for a given seed consists of the first𝑞𝑛𝑠\\mathit\{qns\}questions of every larger sample with the same seed, and the samples with the same seed are therefore nested across sizes\. Each answer is one document\. The human answers form the red setRRand the ChatGPT answers form the blue setBB, so that\|R\|=𝑞𝑛𝑠\|R\|=\\mathit\{qns\}before preprocessing, while\|B\|\|B\|lies between1\.06​𝑞𝑛𝑠1\.06\\,\\mathit\{qns\}and1\.26​𝑞𝑛𝑠1\.26\\,\\mathit\{qns\}in our samples because some questions contribute more than one generated answer\.

##### Tokenization and binarization\.

Every document is first converted to lower case\. HC3 is distributed in Penn Treebank tokenization\[[27](https://arxiv.org/html/2610.41081#bib.bib27)\], in which clitics appear as separate tokens \(for example*should n’t*or*they ’re*\), so the clitics are normalized before words are extracted: the truncated forms*ca n’t*,*wo n’t*and*sha n’t*are expanded to*can not*,*will not*and*shall not*, every remaining*n’t*is rewritten as*not*, and the other clitics \(*’s*,*’re*,*’ve*,*’ll*,*’d*,*’m*\) are removed because their expansion is ambiguous\. The text is then split into words, a word being a maximal sequence of letters and digits, and one\-letter tokens other than*a*and*i*are discarded\. The token*url*, which HC3 substitutes for web links in the human answers, is excluded, since it would separate pairs for a reason unrelated to the language of the texts\. For a thresholdk≥1k\\geq 1, a wordttis considered present in a documentddif it occurs inddat leastkktimes, and the binary incidence matrix is defined byAd​t=1A\_\{dt\}=1ifttis present inddandAd​t=0A\_\{dt\}=0otherwise\. A word is kept as a candidate if it is present in at least two documents and in at most90%90\\,\\%of the documents of the instance, both counts being taken on the binarized matrix\. The standard instances usek=1k=1, that is, plain presence\. The variants usek=2k=2ork=3k=3on the same sample of questions as the corresponding standard instance\. A thresholdk\>1k\>1counts a word only when a text uses it repeatedly \(at leastkktimes\), so a single incidental occurrence no longer separates a pair\. It also yields instances of a different structure, with three to eight times fewer candidates and some pairs separated by very few words, which is why the variants behave differently from the standard instances in Sections[6\.6](https://arxiv.org/html/2610.41081#S6.SS6)and[6\.7](https://arxiv.org/html/2610.41081#S6.SS7)\.

##### Graph\.

Every document is a colored vertex, red forRRand blue forBB, and every candidate word is a neutral vertex\. A word vertexttis adjacent to a document vertexddif and only ifAd​t=1A\_\{dt\}=1, and there are no edges between word vertices\. The document vertices are then completed to a clique, as described above, so that no document vertex separates any pair\. A wordttseparates the pair\(r,b\)\(r,b\)exactly when it is present in one of the two documents and absent from the other, and the covering constraints of the instance are given by the sets

D⁡\(r,b\)=\{t:Ar​t≠Ab​t\},r∈R,b∈B\.D\(r,b\)=\\\{\\,t:A\_\{rt\}\\neq A\_\{bt\}\\,\\\},\\qquad r\\in R,\\ b\\in B\.Completing the documents to a clique and restricting the candidate set to the word vertices yield the same setsD⁡\(r,b\)D\(r,b\), because the clique changes only the neighborhoods of the document vertices\.

##### Inseparable pairs\.

If a red and a blue document have identical rows ofAA, thenD⁡\(r,b\)=∅D\(r,b\)=\\emptysetand the instance has no feasible separator\. This does not happen on any standard instance, but it does happen under the stricter binarization, because a short text retains only a few words whenk≥2k\\geq 2and two different texts can then have the same row\. Such pairs are detected by grouping the documents by their rows, and for every row that is shared by documents of both classes the documents of the smaller class are removed\. Groups with different rows are independent, so this removes the smallest possible number of documents\. This step removes nothing from the standard instances and between zero and four documents on each variant, out of more than 200 documents at𝑞𝑛𝑠=100\\mathit\{qns\}=100and more than 500 at𝑞𝑛𝑠=250\\mathit\{qns\}=250, so the samples remain practically unchanged\.

##### Optimum\-preserving preprocessing\.

Before an instance is written to file, two reductions that do not change the optimum value are applied: documents of the same class with identical rows ofAAare merged, and a wordttis removed when every pair it separates is also separated by another wordt′t^\{\\prime\}\. On vocabularies larger than 3 000 words the second test is applied to a random sample of word pairs, so that some dominated words may remain\. Neither reduction touches the pair constraints, so the kernelization of Section[1\.2](https://arxiv.org/html/2610.41081#S1.SS2), which removes dominated rows and fixes essential words, is still applied by the exact methods on top of them\.

##### Instance set\.

An instance is denoted by the triple\(𝑞𝑛𝑠,𝑠𝑒𝑒𝑑,k\)\(\\mathit\{qns\},\\mathit\{seed\},k\); for example,\(100,42,3\)\(100,42,3\)is the variant withk=3k=3on the sample of 100 questions drawn with seed 42\. In the published files this instance is namedhc3\_q100\_seed42\_k3, and the names of the standard instances carry no suffix\. The benchmark contains 42 instances\. The 32 standard instances usek=1k=1, with𝑞𝑛𝑠∈\{100,150,200\}\\mathit\{qns\}\\in\\\{100,150,200\\\}and seeds 42 to 51, and with𝑞𝑛𝑠=250\\mathit\{qns\}=250and seeds 42 and 43\. The ten variants usek=2k=2andk=3k=3on the samples with𝑞𝑛𝑠=100\\mathit\{qns\}=100and seeds 42, 43 and 44, and on the samples with𝑞𝑛𝑠=250\\mathit\{qns\}=250and seeds 42 and 43\. Table[4](https://arxiv.org/html/2610.41081#S6.T4)summarizes the size of the instances after preprocessing\. The number of red–blue pairs grows quadratically with𝑞𝑛𝑠\\mathit\{qns\}, from about1\.1⋅1041\.1\\cdot 10^\{4\}at𝑞𝑛𝑠=100\\mathit\{qns\}=100to about7⋅1047\\cdot 10^\{4\}at𝑞𝑛𝑠=250\\mathit\{qns\}=250, whereas the number of candidate words grows roughly linearly\. The stricter binarization reduces the candidate set by a factor of three to eight and leaves some pairs that are separated by very few words; on six of the ten variants some pair is separated by a single word, which then belongs to every feasible separator\.

Table 4:Size of the 42 NLP instances after preprocessing, given as the range over the instances of each group\.\|T\|\|T\|: number of candidate words;\|E\|\|E\|: number of document–word edges;\|R\|​\|B\|\|R\|\\,\|B\|: number of red–blue pairs\.
#### 6\.1\.1Sensitivity of theqBBCq\_\{\\text\{BBC\}\}andqLBBDq\_\{\\text\{LBBD\}\}parameters

The complete NLP tuning experiment evaluates

qBBC,qLBBD∈\{1,2,5,10,50,100,500\}q\_\{\\mathrm\{BBC\}\},q\_\{\\mathrm\{LBBD\}\}\\in\\\{1,2,5,10,50,100,500\\\}on all 42 NLP benchmark instances: the 32 standard instances together with the tenk∈\{2,3\}k\\in\\\{2,3\\\}variants\. These results are reported in Appendix[B](https://arxiv.org/html/2610.41081#A2)\. We report mean primal and dual bounds, mean relative optimality gap, number of proven optima, and separation effort over all 42 instances\. We selectedqBBCq\_\{\\text\{BBC\}\}andqLBBDq\_\{\\text\{LBBD\}\}by maximizing the number of proven optima, using the mean relative optimality gap to break ties\.

The completeBbcexperiment confirms that a small cut batch is preferable\.qBBC=2q\_\{\\mathrm\{BBC\}\}=2gives the smallest mean gap, 13\.21%, and proves 16 of the 42 instances optimally\. The only other setting with the same number of certificates isqBBC=10q\_\{\\text\{BBC\}\}=10, but its mean gap is slightly larger \(13\.29%\) and its mean lower bound is slightly weaker \(12\.05 versus 12\.12\)\. TheqBBC=500q\_\{\\text\{BBC\}\}=500setting proves 12 instances optimal, but its mean gap rises to 16\.26%, indicating that very aggressive callback batching is not beneficial forBbc\. We therefore select

qBBC=2\.\\boxed\{q\_\{\\mathrm\{BBC\}\}=2\}\.
ForLbbd,qLBBD=50q\_\{\\text\{LBBD\}\}=50gives the smallest mean gap \(14\.20%\), whereasqLBBD=100q\_\{\\text\{LBBD\}\}=100is very close \(14\.38%\)\. Both values attain the same mean lower bound, 12\.29, butqLBBD=100q\_\{\\text\{LBBD\}\}=100is the only setting that proves 11 instances optimal and it also reduces the average number of master iterations to 18\.4\. TheqLBBD=500q\_\{\\text\{LBBD\}\}=500setting reduces the iteration count further to 11\.8, but its mean gap deteriorates to 15\.23% and the number of certificates drops to 10\. Hence, we retain

qLBBD=100\.\\boxed\{q\_\{\\mathrm\{LBBD\}\}=100\}\.
Figures[4\(a\)](https://arxiv.org/html/2610.41081#S6.F4.sf1)–[4\(d\)](https://arxiv.org/html/2610.41081#S6.F4.sf4)summarize the complete tuning study\.

![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/tuning_nlp_complete_gap.png)\(a\)Mean optimality gap forBbcandLbbdover all 42 NLP instances\.
![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/tuning_nlp_complete_certificates.png)\(b\)Number of the 42 NLP instances proved optimal for each tested parameter value\.
![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/tuning_nlp_complete_lb.png)\(c\)Mean LBs over all 42 NLP instances\.
![Refer to caption](https://arxiv.org/html/2610.41081v1/figures/tuning_nlp_complete_effort.png)\(d\)Mean separation effort \(\# of iterations\) during NLP tuning:Bbccallback invocations andLbbdmaster iterations\.

Figure 4:NLP tuning: summary results forBbcandLbbdover all 42 instances\.

### 6\.2Experimental protocol and coverage

Following the complete tuning study, BBC is run withqBBC=2q\_\{\\mathrm\{BBC\}\}=2and LBBD withqLBBD=100q\_\{\\mathrm\{LBBD\}\}=100\. ILP, GRASP, and VNS follow the same protocol used for theRandombenchmark\. All aggregate comparisons below use all 42 instances unless stated otherwise\.

### 6\.3Overall performance across all approaches

Table[5](https://arxiv.org/html/2610.41081#S6.T5)reports the aggregate results over the complete 42\-instance NLP benchmark\.

Table 5:Overall NLP results on all 42 benchmark instances\. Exact methods report mean UB, mean LB, mean relative gap, and the number of proven optima\.GraspandVnsreport the per\-instance ten\-run mean solution size\.Across all 42 instances,Ilpremains the strongest exact method on the primal side, with mean UB 13\.62\.Bbcfollows with 13\.90, whileLbbdhas mean UB 14\.26\. In contrast, the decomposition methods substantially strengthen the dual side: BBC attains mean LB 12\.12 andLbbdreaches the strongest mean LB, 12\.29, compared with 10\.55 forIlp\. Consequently, BBC has the smallest overall mean optimality gap, 13\.21%, followed byLbbdat 14\.38%, whereasIlpremains at 23\.75%\.

The certificate comparison is similarly favorable toBbc: it proves 16 of the 42 instances optimal, compared with 11 forIlpandLbbdeach\. A Friedman test over the 42 paired exact\-method gaps confirms a significant difference \(χ2=42\.05\\chi^\{2\}=42\.05,p=7\.39×10−10p=7\.39\\times 10^\{\-10\}\)\.

Table[6](https://arxiv.org/html/2610.41081#S6.T6)gives the grouped view over the complete 42\-instance benchmark\. The tenk∈\{2,3\}k\\in\\\{2,3\\\}variants are included in their corresponding NLP\-𝑞𝑛𝑠\\mathit\{qns\}groups; consequently, the number of instances per group are1616for𝑞𝑛𝑠=100\\mathit\{qns\}=100,1010for𝑞𝑛𝑠=150\\mathit\{qns\}=150,1010for𝑞𝑛𝑠=200\\mathit\{qns\}=200, and66for𝑞𝑛𝑠=250\\mathit\{qns\}=250\.

Table 6:Grouped results on all 42 NLP benchmark instances\. TheNNcolumn shows the number of instances contributing to each NLP\-𝑞𝑛𝑠\\mathit\{qns\}group\. Exact methods report mean UB, mean LB, and mean gap; heuristics report ten\-run means\.
### 6\.4Primal heuristic behavior

Across all 42 instances,Graspobtains mean separator size 13\.73, compared with 14\.30 forVns\. At the instance level,Grasphas the smaller ten\-run mean on 31 instances,Vnson 2, and the methods tie on 9\. The paired Wilcoxon signed\-rank test givesp=7\.80×10−7p=7\.80\\times 10^\{\-7\}\. Relative to the best exact incumbent on each instance, the average excess is 0\.76% forGraspand 5\.21% forVns\.

### 6\.5Optimality certificates and dynamic constraint generation

Because MRBSSP has an integer\-valued objective, optimality is counted whenever⌈L​B⌉=U​B\\lceil LB\\rceil=UB\. On the complete 42\-instance benchmark,Bbcsolves 16 instances to proven optimality,IlpandLbbdprove the optimal solutions on 11 instances each\.

The selected cut\-batch values also lead to markedly different separation dynamics\. WithqBBC=2q\_\{\\mathrm\{BBC\}\}=2,Bbcperforms on average 841\.5 callback invocations and adds 1679 lazy constraints over the 42 instances\. WithqLBBD=100q\_\{\\mathrm\{LBBD\}\}=100,Lbbdrequires only 18\.4 master iterations on average while adding 1145 cuts\. These results indicate the architectural difference between the two methods:Bbcbenefits from selective cut insertion inside one branch\-and\-bound tree, whereasLbbdbenefits from larger batches that reduce repeated master re\-optimizations\.

### 6\.6Comparison with a general\-purpose hitting set solver

Once the candidate set is fixed, an NLP instance is a hitting set problem\[[9](https://arxiv.org/html/2610.41081#bib.bib9),[17](https://arxiv.org/html/2610.41081#bib.bib17)\]\. The elements are the candidate words, and every human/ChatGPT pair\(r,b\)\(r,b\)contributes the setD⁡\(r,b\)D\(r,b\)of candidates that occur in exactly one of the two texts\. A set of words separates all pairs if and only if it meets everyD⁡\(r,b\)D\(r,b\), so a minimum hitting set of this family is a minimum separator and any exact hitting set solver must reach the same optimum asIlp,BbcandLbbd\. This gives a direct way to measure how much the problem\-specific machinery contributes\. We converted every instance into the input format of the PACE 2025 challenge, listing all\|R\|​\|B\|\|R\|\\,\|B\|sets explicitly and without any reduction of our own, and ran UzL\[[5](https://arxiv.org/html/2610.41081#bib.bib5)\], which was ranked first in the exact hitting set track of PACE 2025\[[19](https://arxiv.org/html/2610.41081#bib.bib19)\]\. UzL first shrinks the hypergraph with four standard reduction rules \(a set of size one forces its element, an element contained in a single set is dropped, a set that contains another set is dropped, and an element whose sets all contain a second element is dropped\) and then solves a partial MaxSAT formulation with EvalMaxSAT\[[3](https://arxiv.org/html/2610.41081#bib.bib3)\]\. It outputs a solution only after proving its optimality, so a run that reaches the time limit yields neither a solution nor a bound\. The time limit of a UzL job covers the whole job, including reading the input and the reductions, whereas the 3600 s of the exact methods are counted only after their preprocessing and warm start\. To establish a more rigorous comparison, we therefore ran every instance twice, with job limits of 3600 s and 7200 s; the second run gives UzL about as much time for the search itself as the exact methods had\. Each UzL job ran as a single process on one core of a compute node of the same cluster, which matches the single\-threaded setting used for all other methods in Section[5](https://arxiv.org/html/2610.41081#S5)\.

Table 7:UzL andBbcon the three groups of NLP instances\.\|T\|\|T\|: number of candidate words;\|D\|\|D\|: smallest and mean size of the setsD⁡\(r,b\)D\(r,b\); both are given as ranges over the instances of the group\. Single: instances with a pair separated by one word\. UzL: instances whose optimum UzL is able to prove and the time of the shorter of the two runs, which covers the whole job\.Bbc: instances certified under the one\-hour limit and their solver time\.Table[7](https://arxiv.org/html/2610.41081#S6.T7)shows that the outcome differs between the two kinds of instances in the benchmark\. UzL proved the optimum on all 10 variants \(k∈\{2,3\}k\\in\\\{2,3\\\}\) and on none of the 32 standard instances \(k=1k=1\); the longer time limit did not close a single standard instance\. Thek=2k=2variants on𝑞𝑛𝑠=250\\mathit\{qns\}=250are harder\. On\(250,43,2\)\(250,43,2\)UzL did not finish within either limit on the cluster, where several jobs shared a compute node\. A separate run on a workstation with no other load proved the same optimum asBbcin 4540 s; that run only confirms the value and is not used in the comparison of running times\. Every solution UzL returned separates all pairs, has the size certified byBbcand contains all words that the forbid\-one\-word protocol of Section[6\.7](https://arxiv.org/html/2610.41081#S6.SS7)places in the core; on\(250,43,2\)\(250,43,2\), whose optimum is unique, it returns exactly that dictionary\.Bbccloses the same instance in 20 s of solver time, after about 2300 s of preprocessing\. Under the one\-hour time limit,Bbccertifies 16 of the 42 instances \(Table[5](https://arxiv.org/html/2610.41081#S6.T5)\), among them six standard instances on which UzL does not finish even with the doubled time limit\.

The difference follows from the structure of the sets\. On the standard instances the setsD⁡\(r,b\)D\(r,b\)are long and no pair is separated by fewer than three words, so the kernelization of Section[1\.2](https://arxiv.org/html/2610.41081#S1.SS2), which uses rules of the same kind as UzL \(essential vertices, row dominance and column dominance\), finds no essential word and removes at most 0\.7 % of the pair sets\. On the variants it removes between 13 and 94 % of them, and on six of the ten a pair is separated by a single word, which the first reduction rule fixes at once, so the instance shrinks considerably before any search starts\. On the standard instances reductions of this kind can be expected to leave the MaxSAT solver with nearly the full family of 10 800 to 72 750 long clauses\.Bbc, by contrast, never needs most of these constraints: on the standard instances it adds as lazy cuts between 3\.5 and 17\.6 % of the pair constraints that remain after kernelization\.

### 6\.7Structural Interpretation of Optimal Vocabulary Separators

Beyond optimum cardinality, the NLP instances allow us to study the*structure of the optimal solution space*\. For this structural analysis, we reranBbcwith the tuned settingqBBC=2q\_\{\\mathrm\{BBC\}\}=2and a 7200\-second time limit to determine whether the longer run would certify additional instances\. In this experiment, 19 instances were proved optimal\.

LetS⋆S^\{\\star\}be one certified optimal separator of cardinalityz⋆z^\{\\star\}\. For everyv∈S⋆v\\in S^\{\\star\}, we solve the restricted problem with the additional constraint

that is, the corresponding word isforbiddenfrom the separator\. We classify the tested word according to the best primal and dual information obtained for the restricted problem\.

- •Core/mandatory word\.If the restricted problem is infeasible, or its certified integer lower bound satisfies ⌈L​B−v⌉\>z⋆,\\lceil LB\_\{\-v\}\\rceil\>z^\{\\star\},then no optimum of cardinalityz⋆z^\{\\star\}can excludevv\. Hencevvbelongs to every optimal separator and is part of the*optimal core*\. Among such words, we distinguish*objective\-critical*words, for which the restricted optimum is strictly larger thanz⋆z^\{\\star\}, from*feasibility\-critical*words, for which the restricted model is reported infeasible\.
- •Replaceable word\.If the restricted run finds a feasible separator of sizez⋆z^\{\\star\}, then another optimum exists withoutvv\. Thus,vvoccurs in the reference optimum but not in every optimum\.
- •Restrictive–inconclusive word\.If no alternative optimum of sizez⋆z^\{\\star\}is found, but⌈L​B−v⌉≤z⋆\\lceil LB\_\{\-v\}\\rceil\\leq z^\{\\star\}, then the run suggests that forbiddingvvis restrictive, but it does not prove thatvvbelongs to the core\. This category is therefore kept separate from the proven core\.

The structural experiment covers all 19 NLP instances for whichBbcproved optimality when run withqBBC=2q\_\{\\mathrm\{BBC\}\}=2and a 7200 s time limit\. For each instance, one word at a time is forbidden from the corresponding certified optimum, resulting in 272 restrictedBbcruns\. Each run uses a single compute node with the same resources as the experiments in Section[5](https://arxiv.org/html/2610.41081#S5)\. Of these runs, 242 terminate with an integer optimal solution, 17 report infeasibility under the forbidden\-word restriction, and 13 reach the time limit\. A run that reaches the time limit could still prove a word mandatory if its integer lower bound exceedsz⋆z^\{\\star\}, but this did not happen in the present runs\. Instead, 5 of the 13 time\-limit runs proved the forbidden word replaceable, because they found a separator of sizez⋆z^\{\\star\}without it\. The remaining 8 runs are classified as restrictive–inconclusive\.

Overall, the 272 tested words are classified as

113​core/mandatory,151​replaceable,8​restrictive–inconclusive\.\\boxed\{113\\ \\text\{core/mandatory\},\\qquad 151\\ \\text\{replaceable\},\\qquad 8\\ \\text\{restrictive\-\-inconclusive\}\}\.Thus, 41\.54% of the tested words are proved to belong to the optimal core, 55\.51% are proved replaceable, and only 2\.94% remain unresolved\. Among the 113 mandatory words, 96 are objective\-critical and 17 are feasibility\-critical\.

Table[8](https://arxiv.org/html/2610.41081#S6.T8)summarizes the instance\-level structure\. The quantityρcert=\|Ccert\|z⋆\\rho\_\{\\mathrm\{cert\}\}=\\frac\{\|C\_\{\\mathrm\{cert\}\}\|\}\{z^\{\\star\}\}is the fraction of the reference optimum already proved to belong to the core\. When there are no inconclusive words, this is the exact rigidity ratio; when inconclusive words remain, it is a certified lower bound on the true rigidity\. The classification refers to the candidate set after the preprocessing of Section[6\.1](https://arxiv.org/html/2610.41081#S6.SS1), from which a word is removed when another word separates every pair it separates\. Restoring the removed words changes the status of one core word\. On\(250,42,3\)\(250,42,3\)the word*vanderbilt*is present in exactly the same texts as*biltmore*and was removed as its duplicate, so the two words are interchangeable\. Of the other 112 core words, only*lolita*on\(100,43,2\)\(100,43,2\)has a removed word that separates no pair which*lolita*does not separate, namely*film*, and an exact check confirms that*lolita*remains in every optimum when the removed words are restored\.

Table 8:Structural classification of the 272 words belonging to the 19 certifiedBbcoptima\. “Core” denotes words proved mandatory in every optimum; “Repl\.” denotes replaceable words; “Inc\.” denotes restrictive–inconclusive words\.The experiment reveals several qualitatively different types of optimal solution structure\. Two instances are completely rigid:\(100,50,1\)\(100,50,1\)and\(250,43,2\)\(250,43,2\)have respectively10/1010/10and18/1818/18reference\-optimum words proved mandatory\. Since every word of a size\-z⋆z^\{\\star\}optimum belongs to every optimum, the optimal separator is unique in both cases\. Strong but not complete rigidity is observed for\(100,42,3\)\(100,42,3\)and\(250,43,3\)\(250,43,3\)\.

At the opposite extreme, every word in the reference optima of the instances\(100,44,1\)\(100,44,1\),\(100,47,1\)\(100,47,1\),\(100,48,1\)\(100,48,1\), and\(100,51,1\)\(100,51,1\)has been proved replaceable\. Consequently, their optimal cores are empty: no word from the reference optimum occurs in every optimal separator\. The instances\(150,48,1\)\(150,48,1\)and\(200,48,1\)\(200,48,1\)are also highly flexible, with 13 of 14 and 14 of 15 words proved replaceable, respectively, while one word in each instance remains inconclusive\.

The most ambiguous instance is\(100,49,1\)\(100,49,1\)\. Five words are already proved mandatory \(as,error,on,which, andwith\), while six words remain restrictive–inconclusive\. For each of these six words, the restricted run finds only a larger incumbent, but its integer lower bound does not exclude an alternative optimum of sizez⋆=11z^\{\\star\}=11\.

The two kinds of instances differ clearly\. On the nine standard instances only 16 of the 104 tested words are in the core, 15 of them on\(100,49,1\)\(100,49,1\)and\(100,50,1\)\(100,50,1\), and six of the nine instances have an empty core\. On the ten variants 97 of the 168 tested words are in the core, and all 17 feasibility\-critical words occur there\. On the standard instances every pair is separated by at least three words, so an optimum can usually be rearranged without increasing its size\. The stricter binarization of the variants leaves far fewer candidates and some pairs that only a few words separate, and these words become indispensable\.

##### Coverage of the selected words\.

The classification of Table[8](https://arxiv.org/html/2610.41081#S6.T8)can be read against a simple per\-word quantity\. A wordttseparates the pair\(r,b\)\(r,b\)if and only if it occurs in exactly one of the two texts, so the number of pairs it separates is

P⁡\(t\)=dR​\(t\)​\(\|B\|−dB​\(t\)\)\+\(\|R\|−dR​\(t\)\)​dB​\(t\),P\(t\)\\;=\\;d\_\{R\}\(t\)\\,\\bigl\(\|B\|\-d\_\{B\}\(t\)\\bigr\)\+\\bigl\(\|R\|\-d\_\{R\}\(t\)\\bigr\)\\,d\_\{B\}\(t\),wheredR​\(t\)d\_\{R\}\(t\)anddB​\(t\)d\_\{B\}\(t\)are the numbers of human and ChatGPT texts containingtt\. We callP⁡\(t\)P\(t\)the coverage oftt\. Its theoretical maximum\|R\|​\|B\|\|R\|\\,\|B\|would be attained by a word occurring in every text of one class and in none of the other; no such word exists on these instances, and the candidates with the highest coverage are words that occur in about half of the texts of both classes, each separating close to half of all pairs\. Figure[5](https://arxiv.org/html/2610.41081#S6.F5)plots the coverage of every candidate word on four instances chosen to represent the different solution structures of Table[8](https://arxiv.org/html/2610.41081#S6.T8), with the words of the certified optimumS⋆S^\{\\star\}marked by their class\.

Figure 5:CoverageP⁡\(t\)P\(t\)of every candidate word, ordered by rank, on four NLP instances: \(a\) the instance\(100,50,1\)\(100,50,1\), whose optimum is unique; \(b\) the instance\(100,47,1\)\(100,47,1\), whose optimum has an empty core; \(c\) the instance\(100,49,1\)\(100,49,1\), with five core words and six unresolved words; \(d\) the instance\(250,42,3\)\(250,42,3\), with 15 of 25 words in the core\. Stop words and content words are drawn in different colors; the words of the certified optimum are marked as core \(filled\), replaceable \(hollow\) or restrictive–inconclusive \(grey square\)\. The dashed horizontal line distinguishes between the words that separate more than half of the human/ChatGPT pairs \(above the line\) and those that separate fewer\.Three observations hold on all 19 instances, not only on the four shown\. The first is that the optimal separators are built from the top of the coverage curve\. Of the 272 words in the 19 certified optima, 212 are among the 30 highest\-ranked candidates of their instance and 245 are within the top 10 % of the candidates; the median word of an optimum separates 44 % of all pairs on its own\. On the standard instances the top of the curve is made of short function words \(*or*,*as*,*can*,*on*,*with*\), which occur in roughly half of the texts of both classes, and these words make up most of the optimal separators\.

The second observation is that the class of a word is not visible from its coverage\. Core words have a median rank of 11 and replaceable words a median rank of 15; both classes separate a median of 44 % of the pairs, and the two profiles overlap completely\. The unique optimum of\(100,50,1\)\(100,50,1\)in panel \(a\) and the optimum of\(100,47,1\)\(100,47,1\)in panel \(b\), all of whose words are replaceable, occupy the same region of the curve\. Whether a word can be exchanged is therefore decided by*which*pairs it separates relative to the other words, not by how many, and this is precisely the information that the forbid\-one\-word certificates add to the picture\. The third observation concerns the exceptions to the first one, which are the words whose contribution no other word provides\. The core word*error*on\(100,49,1\)\(100,49,1\)ranks 648th of 1 732 candidates and separates 4 % of the pairs; on the instance\(250,42,3\)\(250,42,3\)the core words*area*,*biltmore*\(or its duplicate*vanderbilt*\),*change*and*water*rank between 66th and 425th and separate about 1 % of the pairs each\. These words are mandatory not because they separate many pairs but because they separate a few critical pairs that no high\-coverage word separates; the feasibility\-critical words of the variants are the extreme case, each being the only separator of some pair\. The coverage curve thus accounts for the bulk of the optima, while the structural classification identifies the few words whose contribution is irreplaceable\.

##### Why the selected words are short\.

Function words dominate between the components of optima because the objective minimizes the number of selected words, and on these texts a function word separates far more pairs than a content word\. A content word that occurs inddtexts separates at mostd​max⁡\(\|R\|,\|B\|\)d\\max\(\|R\|,\|B\|\)pairs, a small fraction of the\|R\|​\|B\|\|R\|\\,\|B\|pairs whenddis small, whereas a function word that occurs in about half of the texts of each class separates close to half of all pairs; on the instance\(100,43,1\)\(100,43,1\), the median word with more than five letters separates fewer than 3 % of the pairs\. Restricting the candidate set makes this explicit\. Table[9](https://arxiv.org/html/2610.41081#S6.T9)reports the size of the separator found by the greedy heuristic described below on the 32 standard instances when the candidates are restricted to \(i\) the 143 to 152 stop words of the instance, \(ii\) words of at least four, five or six letters and \(iii\) all words except stop words\. With stop words alone the separator is as small as on the full vocabulary on the 28 instances where the stop words admit a separator \(median ratio 1\.00\), so about 6 % of the vocabulary usually carries the whole separation; on the other four instances the stop words do not separate every pair, because some human/ChatGPT pair differs only in content words\. Excluding stop words makes the separator 1\.4 to 3\.2 times larger \(median 1\.8\), and restricting to words of at least six letters leaves no separating set at all on seven of the 32 instances\. The ratios in the table are taken over the instances on which the restricted candidates admit a separator\. The one ratio below one, 0\.93 on the instance\(150,47,1\)\(150,47,1\), where the stop words alone give 13 words against 14 on the full vocabulary, arises because the greedy heuristic is not monotone in the candidate set: a smaller candidate set can lead it along a different path to a smaller separator\.

Exact solutions of the restricted problems on the standard instances with a certified optimum confirm that this is not a weakness of the heuristic: with words of at least five letters the optimum is 15 to 18 on the𝑞𝑛𝑠=100\\mathit\{qns\}=100instances, 30 on\(150,48,1\)\(150,48,1\)and 36 on\(200,48,1\)\(200,48,1\), against 10 to 15 on the full vocabulary, while stop words alone attain the full\-vocabulary optimum on four of these instances and are within one word of it on three others\. Making content words competitive with high\-coverage function words would therefore require a change of the objective, for instance weighting words by their length or their document frequency; we leave this to future work and keep the pair\-separation objective, whose solutions are what the exact methods certify\.

The heuristic used for Table[9](https://arxiv.org/html/2610.41081#S6.T9)is the classical greedy rule for set covering\[[11](https://arxiv.org/html/2610.41081#bib.bib11)\], applied to the family of setsD⁡\(r,b\)D\(r,b\)restricted to the admissible candidates\. Starting from the empty set, it repeatedly adds the admissible word that separates the largest number of pairs not yet separated\. These pairs are exactly the red–blue pairs whose documents have the same incidence pattern on the words chosen so far, so the gain of a word is its coverageP⁡\(t\)P\(t\)computed within each group of such documents and summed over the groups\. Ties are broken by a fixed order of the words, so the result is deterministic\. The procedure stops when every pair is separated\. If unseparated pairs remain but no admissible word separates any of them, the restricted instance has no feasible separator, and this is how the column*infeasible*of Table[9](https://arxiv.org/html/2610.41081#S6.T9)is obtained\. The size of the greedy separator exceeds the optimum by at most the factorℋ⁡\(maxt⁡P⁡\(t\)\)≤1\+ln⁡\(\|R\|​\|B\|\)\\mathcal\{H\}\(\\max\_\{t\}P\(t\)\)\\leq 1\+\\ln\(\|R\|\\,\|B\|\), whereℋ⁡\(n\)\\mathcal\{H\}\(n\)denotes thenn\-th harmonic number\[[11](https://arxiv.org/html/2610.41081#bib.bib11)\]\. It differs from the randomized construction used by GRASP in Section[2\.2](https://arxiv.org/html/2610.41081#S2.SS2), and the same rule is applied to the full and to every restricted candidate set, so the ratios in Table[9](https://arxiv.org/html/2610.41081#S6.T9)compare solutions of the same heuristic\.

Table 9:Size of the greedy separator when the candidate set is restricted, relative to the greedy separator on the full vocabulary, over the 32 standard instances\.*share*: mean share of the vocabulary that remains a candidate;*infeasible*: instances for which no feasible separator exists within the restricted candidate set\. The ratios are taken over the remaining instances\.These results show that membership in one minimum separator is not, by itself, a sufficient measure of feature importance\. A*replaceable*word can be removed while preserving the optimum cardinality, whereas a*core/mandatory*word is structurally unavoidable across the complete family of optimal separators\. The latter therefore provides a stronger form of vocabulary importance\. Conversely, the restrictive–inconclusive class identifies words for which the current computation provides evidence of importance but not a proof of core membership\. This distinction is useful for interpreting the NLP model because it separates genuinely unavoidable discriminative vocabulary from alternative, mutually substitutable optimal explanations\.

## 7Conclusions

This paper develops and experimentally evaluates a systematic exact and hybrid computational framework for the Minimum Red–Blue Separating Set Problem \(MRBSSP\)\. The framework combines a compact Set\-Cover ILP formulation, safe preprocessing with kernelization, an iterative Logic\-Based Benders Decomposition \(LBBD\), and a Branch\-and\-Benders\-Cut \(BBC\) algorithm\. GRASP approach is used both as a standalone heuristic and as a source of validated warm starts and upper bounds for the exact approaches, while the VNS approach provides an additional literature\-based heuristic baseline\. The computational study is deliberately organized around two complementary benchmark families: a broadRandomgraph benchmark for controlled algorithmic stress testing and an NLP\-derived benchmark that connects MRBSSP with interpretable vocabulary selection for distinguishing human\- and AI\-generated texts\.

TheRandombenchmark contains 250 instances arranged across graph sizes and densities, of which 200 are feasible\. This benchmark exposes clear complementarity among the exact approaches\. The best parameter choice of the BBC approach adds at mostqBBC=5q\_\{\\mathrm\{BBC\}\}=5lazy cuts per callback and LBBD at mostqLBBD=100q\_\{\\mathrm\{LBBD\}\}=100cuts per master iteration\. ILP gives the strongest primal performance, with mean a UB of 18\.83\. BBC proves the largest number of instances optimal, 92 out of 200, whereas LBBD gives the strongest mean lower bound, 13\.63, and the smallest mean optimality gap, 24\.37%\. On the 11 groups not solved completely by all exact methods, the mean group gaps are 53\.71% for ILP, 47\.21% for BBC, and 44\.30% for LBBD\. The repeated\-run heuristic study additionally shows that both meta\-heuristic approaches, GRASP and VNS, produce strong feasible solutions with low run\-to\-run variability\. Thus, theRandombenchmark provides a broad view of the trade\-off between primal quality, dual\-bound progress, and certification strength\.

The NLP benchmark provides a second and substantially different test of the same algorithms\. The complete parameter study overqLBBD,qBBC∈\{1,2,5,10,50,100,500\}q\_\{\\text\{LBBD\}\},q\_\{\\text\{BBC\}\}\\in\\\{1,2,5,10,50,100,500\\\}selectsqBBC=2q\_\{\\mathrm\{BBC\}\}=2andqLBBD=100q\_\{\\mathrm\{LBBD\}\}=100\. Across all 42 NLP instances, ILP remains the strongest primal exact method, with a mean upper bound of 13\.62\. BBC attains the smallest mean optimality gap \(13\.21%\) and proves the largest number of optima \(16\), while LBBD provides the strongest mean lower bound of 12\.29\. TheqLBBD=500q\_\{\\text\{LBBD\}\}=500experiments confirm that increasing cut batches beyond the selected values does not improve the final trade\-off\.

The NLP benchmark also demonstrates that the value of an exact solution is not limited to its objective cardinality\. By forbidding vertices from certified optimal separators one at a time, we distinguish mandatory vocabulary features from replaceable ones\. The structural experiment covers the 19 NLP instances for which BBC certifies optimality under the extended computational limit, resulting in 272 restricted BBC runs\. Overall, 113 of the tested vocabulary features are proved to be core/mandatory, 151 are proved replaceable, and only 8 remain restrictive–inconclusive\. Thus, approximately 41\.54% of the tested words are certified as belonging to the optimal core, whereas 55\.51% are replaceable and 2\.94% remain unresolved\. Among the 113 mandatory words, 96 are objective\-critical and 17 are feasibility\-critical\. Some instances admit highly non\-unique optimal vocabularies, including cases with an empty certified core, whereas others exhibit completely or almost completely rigid optimal separators\. This structural analysis provides a stronger interpretation of feature importance than reporting a single minimum separator, since it distinguishes features that are unavoidable across all optimal solutions from those that can be substituted without increasing the objective value\.

Taken together, the two benchmark families provide complementary evidence\. The study on theRandombenchmark emphasizes robustness across graph size and density, whereas the NLP study demonstrates that the same exact and hybrid methodology remains effective on structured real\-data graphs and can additionally support an interpretable analysis of the complete optimal\-solution structure\. Across both benchmarks, no single exact method dominates every computational criterion: ILP is generally strongest on primal solution quality, LBBD is particularly effective in producing stronger dual bounds, and BBC is highly competitive in optimality certification\. The heuristic approaches complement the exact methods by supplying high\-quality feasible solutions and, in the case of GRASP, useful warm starts and upper bounds for the exact search\.

Future work should enlarge both benchmark families, especially by adding more structurally diverse real\-data instances, and should investigate stronger problem\-specific reductions, adaptive cut\-batch policies for BBC and LBBD, and alternative cut\-ranking strategies\. On the application side, natural extensions include weighted or cost\-sensitive vocabulary separators, robustness to perturbations of the text\-feature incidence matrix, and multi\-class generalizations in which several text\-generation sources must be distinguished simultaneously\. A further direction is to exploit the mandatory/replaceable feature analysis directly within the optimization process, for example to identify persistent core features across multiple optimal or near\-optimal separators\.

## Acknowledgements

This publication is co\-funded by the European Union’s Horizon Europe research and innovation programme under the Marie Skłodowska\-Curie COFUND Postdoctoral Programme, grant agreement No\. 101081355–SMASH, and by the Republic of Slovenia and the European Union from the European Regional Development Fund\. Co\-funded by the European Union\. Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Executive Agency \(REA\)\. Neither the European Union nor the REA can be held responsible for them\.

## References

- \[1\]S\. Acid and L\. M\. De Campos\. An algorithm for finding minimum d\-separating sets in belief networks\. In*Proceedings of the Twelfth International Conference on Uncertainty in Artificial Intelligence*, Portland, OR, USA, 1996, pp\. 3–10\.
- \[2\]Alber, J\., & Fiala, J\. \(2004\)\. Geometric separation and exact solutions for the parameterized independent set problem on disk graphs\.*Journal of Algorithms*, 52\(2\), 134–151\.
- \[3\]Avellaneda, F\. \(2020\)\. A short description of the solver EvalMaxSAT\. In*MaxSAT Evaluation 2020: Solver and Benchmark Descriptions*\(pp\. 8–9\)\. Department of Computer Science Report Series B, B\-2020\-2, University of Helsinki\.
- \[4\]Balas, E\., & Padberg, M\. W\. \(1976\)\. Set partitioning: A survey\.*SIAM Review*, 18\(4\), 710–760\.
- \[5\]Bannach, M\., Chudigiewitsch, F\., & Wienöbst, M\. \(2025\)\. PACE solver description: UzL solver for dominating set and hitting set\. In A\. Agrawal & E\. J\. van Leeuwen \(Eds\.\),*20th International Symposium on Parameterized and Exact Computation \(IPEC 2025\)*\(Leibniz International Proceedings in Informatics, Vol\. 358, pp\. 39:1–39:4\)\. Schloss Dagstuhl – Leibniz\-Zentrum für Informatik\.[https://doi\.org/10\.4230/LIPIcs\.IPEC\.2025\.39](https://doi.org/10.4230/LIPIcs.IPEC.2025.39)\.
- \[6\]Benders, J\. F\. \(1962\)\. Partitioning procedures for solving mixed\-variables programming problems\.*Numerische Mathematik*, 4, 238–252\.
- \[7\]Caprara, A\., Toth, P\., & Fischetti, M\. \(2000\)\. Algorithms for the set covering problem\.*Annals of Operations Research*, 98, 353–371\.
- \[8\]Carr, R\. D\., Doddi, S\., Konjevod, G\., & Marathe, M\. V\. \(2000\)\. On the red\-blue set cover problem\. In*Proceedings of the 11th Annual ACM–SIAM Symposium on Discrete Algorithms \(SODA\)*\(pp\. 345–353\)\.
- \[9\]Chandrasekaran, K\., Karp, R\., Moreno\-Centeno, E\., & Vempala, S\. \(2011\)\. Algorithms for implicit hitting set problems\. In*Proceedings of the 22nd Annual ACM–SIAM Symposium on Discrete Algorithms \(SODA\)*\(pp\. 614–629\)\. SIAM\.
- \[10\]Christofides, N\., & Korman, S\. \(1975\)\. A computational survey of methods for the set covering problem\.*Management Science*, 21\(5\), 591–599\.
- \[11\]Chvátal, V\. \(1979\)\. A greedy heuristic for the set\-covering problem\.*Mathematics of Operations Research*, 4\(3\), 233–235\.
- \[12\]Codato, G\., & Fischetti, M\. \(2006\)\. Combinatorial Benders’ cuts for mixed\-integer linear programming\.*Operations Research*, 54\(4\), 756–766\.
- \[13\]Dev, S\. R\., Dey, S\., Foucaud, F\., Klasing, R\., & Lehtilä, T\. \(2023\)\. The red\-blue separation problem on graphs\.*Theoretical Computer Science*, 971, 114071\.
- \[14\]Feige, U\. \(1998\)\. A threshold ofln⁡n\\ln nfor approximating set cover\.*Journal of the ACM*, 45\(4\), 634–652\.
- \[15\]Feo, T\. A\., & Resende, M\. G\. C\. \(1995\)\. Greedy randomized adaptive search procedures\.*Journal of Global Optimization*, 6, 109–133\.
- \[16\]Forman, G\. \(2003\)\. An extensive empirical study of feature selection metrics for text classification\.*Journal of Machine Learning Research*, 3, 1289–1305\.
- \[17\]Gainer\-Dewar, A\., & Vera\-Licona, P\. \(2017\)\. The minimal hitting set generation problem: Algorithms and computation\.*SIAM Journal on Discrete Mathematics*, 31\(1\), 63–100\.
- \[18\]Gehrmann, S\., Strobelt, H\., & Rush, A\. M\. \(2019\)\. GLTR: Statistical detection and visualization of generated text\. In*Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics: System Demonstrations*\(pp\. 111–116\)\.
- \[19\]Grobler, M\., & Siebertz, S\. \(2025\)\. The PACE 2025 Parameterized Algorithms and Computational Experiments Challenge: Dominating set and hitting set\. In A\. Agrawal & E\. J\. van Leeuwen \(Eds\.\),*20th International Symposium on Parameterized and Exact Computation \(IPEC 2025\)*\(Leibniz International Proceedings in Informatics, Vol\. 358, pp\. 32:1–32:17\)\. Schloss Dagstuhl – Leibniz\-Zentrum für Informatik\.[https://doi\.org/10\.4230/LIPIcs\.IPEC\.2025\.32](https://doi.org/10.4230/LIPIcs.IPEC.2025.32)\.
- \[20\]Guo, B\., Zhang, X\., Wang, Z\., Jiang, M\., Nie, J\., Ding, Y\., Yue, J\., & Wu, Y\. \(2023\)\. How close is ChatGPT to human experts? Comparison corpus, evaluation, and detection\.*arXiv preprint arXiv:2301\.07597*\.
- \[21\]Herbold, S\., Hautli\-Janisz, A\., Heuer, U\., Kikteva, Z\., & Trautsch, A\. \(2023\)\. A large\-scale comparison of human\-written versus ChatGPT\-generated essays\.*Scientific Reports*, 13, 18617\.
- \[22\]Hochbaum, D\. S\. \(1997\)\. Approximating covering and packing problems: Set cover, vertex cover, independent set, and related problems\. In D\. S\. Hochbaum \(Ed\.\),*Approximation Algorithms for NP\-Hard Problems*\(pp\. 94–143\)\. PWS Publishing\.
- \[23\]Hooker, J\. N\., & Ottosson, G\. \(2003\)\. Logic\-based Benders decomposition\.*Mathematical Programming*, 96, 33–60\.
- \[24\]Kobak, D\., González\-Márquez, R\., Horvát, E\.\-Á\., & Lause, J\. \(2025\)\. Delving into LLM\-assisted writing in biomedical publications through excess vocabulary\.*Science Advances*, 11, eadt3813\.[https://doi\.org/10\.1126/sciadv\.adt3813](https://doi.org/10.1126/sciadv.adt3813)\.
- \[25\]Krak, I\., Barmak, O\., Manziuk, E\., & Kulias, A\. \(2019\)\. Data classification based on the features reduction and piecewise linear separation\. In*Proceedings of the International Conference on Intelligent Computing & Optimization*\(pp\. 282–289\)\. Springer\.
- \[26\]Liu, H\., Cao, Z\., Long, M\., Wang, J\., & Yang, Q\. \(2019\)\. Separate to adapt: Open set domain adaptation via progressive separation\. In*Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition \(CVPR\)*\(pp\. 2922–2931\)\.
- \[27\]Marcus, M\. P\., Santorini, B\., & Marcinkiewicz, M\. A\. \(1993\)\. Building a large annotated corpus of English: The Penn Treebank\.*Computational Linguistics*, 19\(2\), 313–330\.
- \[28\]Milojković, D\. \(2025\)\. Variable neighborhood search for red–blue separating set in graphs\.*IPSI Transactions on Internet Research*, 21\(1\), 119–128\.[https://doi\.org/10\.58245/ipsi\.tir\.2501\.11](https://doi.org/10.58245/ipsi.tir.2501.11)\.
- \[29\]Mitchell, E\., Lee, Y\., Khazatsky, A\., Manning, C\. D\., & Finn, C\. \(2023\)\. DetectGPT: Zero\-shot machine\-generated text detection using probability curvature\. In*Proceedings of the 40th International Conference on Machine Learning \(ICML\)*\(PMLR, Vol\. 202, pp\. 24950–24962\)\.
- \[30\]Mladenović, N\., & Hansen, P\. \(1997\)\. Variable neighborhood search\.*Computers & Operations Research*, 24\(11\), 1097–1100\.
- \[31\]Pearce, R\. H\. \(2019\)\.*Towards a general formulation of lazy constraints*\[Doctoral dissertation, School of Mathematics and Physics, The University of Queensland\]\.
- \[32\]Ralphs, T\. K\., & Galati, M\. V\. \(2006\)\. Decomposition and dynamic cut generation in integer linear programming\.*Mathematical Programming*, 106\(2\), 261–285\.[https://doi\.org/10\.1007/s10107\-005\-0606\-3](https://doi.org/10.1007/s10107-005-0606-3)\.
- \[33\]Saharidis, G\. K\. D\., & Ierapetritou, M\. G\. \(2010\)\. Improving Benders decomposition using maximum feasible subsystem \(MFS\) cut generation strategy\.*Computers & Chemical Engineering*, 34\(8\), 1237–1245\.[https://doi\.org/10\.1016/j\.compchemeng\.2009\.10\.002](https://doi.org/10.1016/j.compchemeng.2009.10.002)\.
- \[34\]Skowron, A\., & Rauszer, C\. \(1992\)\. The discernibility matrices and functions in information systems\. In R\. Słowiński \(Ed\.\),*Intelligent Decision Support: Handbook of Applications and Advances of the Rough Sets Theory*\(pp\. 331–362\)\. Kluwer Academic Publishers\.
- \[35\]Vinterbo, S\. A\., & Øhrn, A\. \(2000\)\. Minimal approximate hitting sets and rule templates\.*International Journal of Approximate Reasoning*, 25\(2\), 123–143\.[https://doi\.org/10\.1016/S0888\-613X\(00\)00051\-7](https://doi.org/10.1016/S0888-613X(00)00051-7)\.
- \[36\]Weihe, K\. \(1998\)\. Covering trains by stations or the power of data reduction\. In*Proceedings of the 1998 Algorithms and Experiments Conference \(ALEX ’98\)*\(pp\. 1–8\)\.
- \[37\]Wu, J\., Yang, S\., Zhan, R\., Yuan, Y\., Chao, L\. S\., & Wong, D\. F\. \(2025\)\. A survey on LLM\-generated text detection: Necessity, methods, and future directions\.*Computational Linguistics*, 51\(1\), 275–338\.
- \[38\]Yang, Y\., & Pedersen, J\. O\. \(1997\)\. A comparative study on feature selection in text categorization\. In*Proceedings of the 14th International Conference on Machine Learning \(ICML\)*\(pp\. 412–420\)\.

## Appendix ANumerical results ofqBBCq\_\{\\texttt\{BBC\}\}andqLBBDq\_\{\\texttt\{LBBD\}\}parameter tuning on the benchmark setRandom

Table 10:Bbcapproach tuned on 20 selectedRandominstances\.Table 11:Lbbdapproach tuned on 20 selectedRandominstances\.
## Appendix BNumerical results ofqBBCq\_\{\\texttt\{BBC\}\}andqLBBDq\_\{\\texttt\{LBBD\}\}parameter tuning on the NLP problem instances

Table 12:Bbctuned on all 42 NLP benchmark instances\. “Rounds” denotes the mean number of callback invocations\. The selected setting is shown in bold\.Table 13:Lbbdtuned on all 42 NLP benchmark instances\. “Rounds” denotes the mean number of master iterations\. The selected setting is shown in bold\.
## Appendix CWord\-level classification of words in the optimal solutions of NLP instances solved byBbc

The following lists give the status of every tested word\. Node IDs are shown in parentheses\. A dagger \(†\) marks a feasibility\-critical core word; all other core words are objective\-critical\.

##### \(100,42,2\)\(100,42,2\)\(z⋆=12z^\{\\star\}=12\)\.

Core/mandatory:more\(471\),on\(495\)\. Replaceable:are\(240\),as\(243\),be\(250\),help\(390\),if\(402\),in\(406\),is\(427\),of\(491\),will\(678\),your\(685\)\. Restrictive–inconclusive:–\.

##### \(100,42,3\)\(100,42,3\)\(z⋆=15z^\{\\star\}=15\)\.

Core/mandatory:a\(191\),are\(207\),as\(209\),be\(211\),in\(276\),is\(288\),it\(289\),of\(316\),on\(318\),or\(321\),that\(375\),to\(386\),you\(415\)\. Replaceable:create\(230\),when\(406\)\. Restrictive–inconclusive:–\.

##### \(100,43,1\)\(100,43,1\)\(z⋆=10z^\{\\star\}=10\)\.

Core/mandatory:or\(1380\)\. Replaceable:also\(315\),as\(355\),between\(423\),but\(463\),from\(927\),important\(1056\),like\(1178\),when\(1999\),you\(2037\)\. Restrictive–inconclusive:–\.

##### \(100,43,2\)\(100,43,2\)\(z⋆=14z^\{\\star\}=14\)\.

Core/mandatory:i\(460\)†,lolita\(510\)†\. Replaceable:and\(235\),as\(244\),be\(259\),by\(277\),can\(279\),for\(407\),foreign\(409\),it\(485\),or\(567\),that\(694\),which\(752\),you\(772\)\. Restrictive–inconclusive:–\.

##### \(100,43,3\)\(100,43,3\)\(z⋆=15z^\{\\star\}=15\)\.

Core/mandatory:and\(203\),for\(274\),from\(277\),of\(351\),that\(412\),to\(426\),you\(455\)\. Replaceable:a\(194\),guidance\(292\),in\(306\),more\(340\),not\(347\),on\(352\),the\(413\),was\(439\)\. Restrictive–inconclusive:–\.

##### \(100,44,1\)\(100,44,1\)\(z⋆=11z^\{\\star\}=11\)\.

Core/mandatory:–\. Replaceable:for\(833\),have\(915\),how\(959\),important\(978\),in\(981\),more\(1190\),on\(1264\),there\(1734\),they\(1737\),was\(1840\),with\(1873\)\. Restrictive–inconclusive:–\.

##### \(100,44,2\)\(100,44,2\)\(z⋆=11z^\{\\star\}=11\)\.

Core/mandatory:as\(233\),not\(499\),on\(508\),that\(616\),with\(682\),you\(689\)\. Replaceable:are\(231\),be\(246\),is\(435\),their\(618\),to\(632\)\. Restrictive–inconclusive:–\.

##### \(100,44,3\)\(100,44,3\)\(z⋆=14z^\{\\star\}=14\)\.

Core/mandatory:about\(185\)†,and\(192\),in\(268\),is\(275\),it\(276\),to\(371\)\. Replaceable:a\(184\),for\(246\),if\(266\),of\(308\),on\(311\),that\(360\),their\(362\),you\(402\)\. Restrictive–inconclusive:–\.

##### \(100,47,1\)\(100,47,1\)\(z⋆=11z^\{\\star\}=11\)\.

Core/mandatory:–\. Replaceable:as\(358\),by\(465\),can\(476\),for\(890\),it\(1091\),on\(1318\),or\(1332\),there\(1786\),when\(1915\),would\(1944\),years\(1950\)\. Restrictive–inconclusive:–\.

##### \(100,48,1\)\(100,48,1\)\(z⋆=11z^\{\\star\}=11\)\.

Core/mandatory:–\. Replaceable:about\(228\),if\(978\),make\(1125\),not\(1228\),on\(1253\),or\(1272\),other\(1278\),so\(1581\),this\(1693\),use\(1768\),with\(1834\)\. Restrictive–inconclusive:–\.

##### \(100,49,1\)\(100,49,1\)\(z⋆=11z^\{\\star\}=11\)\.

Core/mandatory:as\(344\),error\(745\),on\(1278\),which\(1907\),with\(1918\)\. Replaceable:–\. Restrictive–inconclusive:at\(351\),be\(377\),by\(441\),do\(678\),important\(983\),other\(1301\)\.

##### \(100,50,1\)\(100,50,1\)\(z⋆=10z^\{\\star\}=10\)\.

Core/mandatory:also\(292\),as\(340\),but\(452\),can\(465\),from\(899\),have\(967\),other\(1350\),so\(1697\),these\(1823\),with\(1972\)\. Replaceable:–\. Restrictive–inconclusive:–\.

##### \(100,51,1\)\(100,51,1\)\(z⋆=11z^\{\\star\}=11\)\.

Core/mandatory:–\. Replaceable:and\(330\),as\(357\),at\(365\),but\(455\),can\(467\),for\(855\),no\(1213\),on\(1240\),other\(1257\),this\(1694\),when\(1807\)\. Restrictive–inconclusive:–\.

##### \(150,48,1\)\(150,48,1\)\(z⋆=14z^\{\\star\}=14\)\.

Core/mandatory:–\. Replaceable:an\(448\),are\(486\),for\(1218\),has\(1336\),i\(1399\),in\(1414\),it\(1491\),like\(1563\),of\(1779\),on\(1790\),their\(2439\),which\(2628\),with\(2646\)\. Restrictive–inconclusive:you\(2671\)\.

##### \(200,48,1\)\(200,48,1\)\(z⋆=15z^\{\\star\}=15\)\.

Core/mandatory:–\. Replaceable:also\(573\),an\(591\),as\(655\),for\(1640\),important\(1887\),not\(2334\),of\(2368\),on\(2384\),that\(3238\),there\(3247\),they\(3250\),with\(3498\),you\(3527\),your\(3530\)\. Restrictive–inconclusive:in\(1891\)\.

##### \(250,42,2\)\(250,42,2\)\(z⋆=18z^\{\\star\}=18\)\.

Core/mandatory:by\(656\),i\(979\)†,in\(991\),one\(1189\)†,you\(1600\)\. Replaceable:a\(532\),and\(574\),as\(588\),for\(881\),have\(945\),is\(1028\),it\(1030\),not\(1170\),on\(1187\),or\(1194\),that\(1477\),there\(1484\),to\(1500\)\. Restrictive–inconclusive:–\.

##### \(250,42,3\)\(250,42,3\)\(z⋆=25z^\{\\star\}=25\)\.

Core/mandatory:a\(476\),and\(490\),are\(495\),area\(496\)†,biltmore\(520\)†,change\(543\)†,in\(683\),is\(704\)†,it\(705\),not\(762\),of\(767\)†,that\(896\),to\(912\)†,water\(936\),you\(956\)\. Replaceable:an\(489\),be\(509\),called\(533\),he\(660\),on\(769\),or\(773\),people\(790\),state\(876\),states\(877\),was\(934\)\. Restrictive–inconclusive:–\.

##### \(250,43,2\)\(250,43,2\)\(z⋆=18z^\{\\star\}=18\)\.

Core/mandatory:can\(666\),for\(933\),have\(1006\),i\(1045\)†,in\(1058\),is\(1094\),it\(1098\),lolita\(1149\)†,more\(1206\),not\(1238\),on\(1256\),or\(1264\),that\(1530\),they\(1539\),to\(1551\),was\(1610\),which\(1627\),you\(1651\)\. Replaceable:–\. Restrictive–inconclusive:–\.

##### \(250,43,3\)\(250,43,3\)\(z⋆=26z^\{\\star\}=26\)\.

Core/mandatory:a\(488\),an\(502\),and\(503\)†,as\(514\),film\(649\),for\(660\),has\(692\),his\(706\),i\(713\)†,in\(720\),is\(734\),it\(735\),not\(810\),of\(819\),penguins\(845\)†,star\(930\),that\(954\),the\(955\)†,they\(962\),to\(969\),water\(994\),you\(1014\),your\(1015\)\. Replaceable:banks\(524\),guidance\(688\),was\(993\)\. Restrictive–inconclusive:–\.