跳转至

文章背景与核心概要

Model-RB 基准测试实例 frb100-40 作为困扰学术界二十多年的公开挑战，其公开记录自 2014 年以来一直停留在 100 个变量中的 99 个，如今该问题终于得到了彻底解决。本文引入了一个可直接检查的、针对该实例 4,000 个顶点图的 100 顶点独立集。结合已验证的 100 个大小为 40 的团划分，该证明确凿无误地证实了该实例的最大独立集大小为 100，最小顶点覆盖大小为 3,900。

这项研究不仅给出了长达二十年的悬案一个完美的定论，还在方法论上通过包含 8,668 次有效运行的预注册活动评估了修复算子，并通过开源的复现工件确保了结果的完全可复现性。该成果展示了离散数学与人工智能在解决极端组合优化难题方面的最新进展。

frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study

After remaining an open challenge for more than two decades—with its public record stalled at 99 out of 100 variables since 2014—the Model-RB benchmark instance frb100-40 has finally been settled.

arXiv： 2609.02804 [cs.DM]
提交时间： 2026年9月2日
作者： Onur Uğurlu (伊兹密尔巴克尔恰伊大学 / İzmir Bakırçay University)
研究主题： 离散数学 (cs.DM)；人工智能 (cs.AI)

执行摘要

This paper introduces a directly checkable 100-vertex independent set for the instance's 4,000-vertex graph. When combined with a verified partition into 100 cliques of size 40, this witness definitively proves that: * 最大独立集大小为 100。 * 最小顶点覆盖大小为 3,900。

核心发现与方法论

  • 搜索与评估： 发现该见证（witness）的随机运行与形式化证明保持了解耦。作者在包含 8,668 次有效运行的预注册活动中评估了新增的成对与三元修复算子。

    • Search & Evaluation: The stochastic run that discovered the witness was kept separate from the formal proof. The author evaluated added pair and triple repair operators in a preregistered campaign comprising 8,668 valid runs.

  • 性能比较：

  • 主要比较未检测到相比基础 ULSA 算法的显著加速（风险比：\(0.967\)，95% 置信区间：\(0.915\text{--}1.023\)；\(p = 0.248\)），这一结论通过析因消融得到了进一步强化。

  • 在较小的 FRB 套件上，具备群感知（group-aware）约束满足问题（CSP）流水线成功求解了 2,500 次运行中的 2,500 次，而 LibMVC-NuMVC 的成功次数为 2,391/2,500。

    • Performance Comparisons:
    • The primary comparison detected no significant acceleration over the base ULSA algorithm (hazard ratio: \(0.967\), 95% confidence interval: \(0.915\text{--}1.023\); \(p = 0.248\)), a conclusion reinforced by factorial ablation.
    • On a smaller FRB suite, a group-aware Constraint Satisfaction Problem (CSP) pipeline successfully solved 2,500 out of 2,500 runs, compared to 2,391 out of 2,500 for LibMVC-NuMVC.

  • 搜索瓶颈： 在 frb100-40 上，完整的 ULSA、基础 ULSA 以及 NuMVC 均产生了 \(0/56\) 的新证书。穷举枚举表明，在三阶汉明半径（Hamming radius of three）内，108 个独特的记录冲突二态中没有一个具有严格改进的群感知 CSP 邻居。

    • Search Barriers: On frb100-40, full ULSA, base ULSA, and NuMVC each produced \(0/56\) new certificates. Exhaustive enumeration demonstrated that none of the 108 unique recorded conflict-two states possessed a strictly improving group-aware CSP neighbor within a Hamming radius of three.

资源与可复现性