Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation

Marko Djukanović, Staša Vujičić Stanković, Žiga Zebec, Christian BlumarXiv 2026 · arXiv

TL;DR

This paper introduces a high-performance optimization framework for the Minimum Red–Blue Separating Set Problem (MRBSSP), a challenge in graph theory with significant implications for data classification. By combining exact mathematical programming with clever decomposition techniques, the authors successfully apply this framework to a timely real-world problem: identifying the smallest set of vocabulary features that can perfectly distinguish human-written text from AI-generated content.

What Problem Does This Paper Address?

Imagine you have two groups of objects—say, "Red" and "Blue"—and you want to tell them apart using the fewest possible "tests" or "features." In graph terms, this is the MRBSSP. You are looking for the smallest set of vertices $S$ such that for every possible pair of one red vertex and one blue vertex, there is at least one vertex in $S$ that "separates" them (meaning the separator's neighbors include one member of the pair, but not both).

While this sounds like a standard "Set Cover" problem, it scales poorly. If you have 500 red nodes and 500 blue nodes, a naive model must handle 250,000 constraints simultaneously. This paper tackles the computational bottleneck of solving this problem exactly on large, complex graphs and explores its utility in Natural Language Processing (NLP) to find the "fingerprints" of AI vs. human text.

Methods

The authors propose a multi-pronged algorithmic strategy:

  1. Preprocessing (Kernelization): Before the heavy lifting begins, they use "safe" rules to shrink the problem, such as identifying "essential" vertices that must be in the solution and removing redundant constraints.
  2. GRASP (Greedy Randomized Adaptive Search Procedure): A fast heuristic used to find high-quality "good enough" solutions quickly. These solutions serve as a "warm start" for the more rigorous exact methods.
  3. Exact Decomposition Methods: Instead of solving one massive problem, they use two sophisticated approaches:
  4. Logic-Based Benders Decomposition (LBBD): This iteratively solves a smaller "master" problem and adds only the specific constraints that are violated.
  5. Branch-and-Benders-Cut (BBC): This is the "gold standard" approach here. It embeds a feasibility checker directly into a single search tree, adding "lazy constraints" only when needed.

The authors provide a baseline for the classical approach in their Algorithm 1:

Algorithm 1: The baseline ILP approach with preprocessing and warm starts.

Datasets

The study evaluates these algorithms on two distinct benchmarks:

  • RANDOM Benchmark: 250 synthetically generated graphs of varying sizes (up to 500 vertices) and densities. This serves as a "stress test" for the algorithms' raw computational power.
  • NLP Benchmark: A new real-world dataset derived from the HC3 (Human ChatGPT Comparison Corpus). It consists of 42 instances where "Red" nodes are human answers and "Blue" nodes are ChatGPT answers. The features (potential separators) are vocabulary words.

Key Insights and Ideas

  • The Power of Laziness: The most effective way to solve MRBSSP isn't to be smarter about the math, but to be "lazier." By using Branch-and-Benders-Cut (BBC), the solver avoids processing thousands of irrelevant constraints, focusing only on the "hard" pairs that are difficult to separate.
  • Complementary Strengths: There is no "one size fits all" algorithm. The authors found that while standard ILP is great at finding good feasible solutions, LBBD is better at proving how far those solutions are from the theoretical best (lower bounds), and BBC is the fastest at proving a solution is truly optimal.
  • Mandatory vs. Replaceable Features: In the NLP application, the authors discovered that some words are "core" (mandatory)—they appear in every possible optimal set of separators. Others are "replaceable," meaning you can swap them for different words without losing the ability to distinguish AI from human text. This highlights that there are many different, equally valid ways to "catch" an AI.

Key Results

  • Efficiency: On the RANDOM benchmark, the tuned BBC approach certified optimality for 92 out of 200 feasible instances, outperforming the other exact methods in frequency of proof.
  • NLP Performance: In the human-AI text separation task, BBC achieved the smallest mean optimality gap and certified 16 optima across 42 instances.
  • Interpretability: The structural analysis identified 113 mandatory vocabulary features and 151 replaceable ones. Interestingly, "stop words" (common words like the, and, or) often dominated the optimal separators because they appear with different frequencies in AI vs. human text, making them highly efficient discriminators.

Limitations and Future Work

The authors acknowledge that while their methods are powerful, the NLP application is currently a "tool for inspection" rather than a real-time detector. It works on a fixed sample of text but hasn't been tested for generalizing to entirely unseen documents.

Future directions include:

  • Scaling the algorithms to even larger datasets.
  • Developing "cost-sensitive" separators (e.g., finding separators that prefer shorter words or specific parts of speech).
  • Extending the problem to "multi-class" separation (e.g., distinguishing between Human, GPT-4, and Claude simultaneously).

Summary updated

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.
BibTeX
@misc{djukanovic2026optimization,
  author = {Marko Djukanović and Staša Vujičić Stanković and Žiga Zebec and Christian Blum},
  title = {{Optimization Techniques for Solving the Minimum Red--Blue Separating Set Problem with an Application to Human--AI Text Separation}},
  year = {2026},
  eprint = {2610.41081},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41081},
}
Figure