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

arXiv: https://arxiv.org/abs/2609.02804 · HTML: https://mlsanity.com/paper/2609.02804/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 23 references that are in the map.
- First posted on arXiv 2 Sep 2026.

## Builds on (most cited first, 6 of 6)

- [Improving Reproducibility in Machine Learning Research (A Report from the NeurIPS 2019 Reproducibility Program)](https://mlsanity.com/paper/2003.12206/) (2020)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Exact Algorithms for Maximum Independent Set](https://mlsanity.com/paper/1312.6260/) (2013)
- [Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover](https://mlsanity.com/paper/1411.2680/) (2014)
- [NuMVC: An Efficient Local Search Algorithm for Minimum Vertex Cover](https://mlsanity.com/paper/1402.0584/) (2014)
- [Unweighted Stochastic Local Search can be Effective for Random CSP Benchmarks](https://mlsanity.com/paper/1411.7480/) (2014)

## Abstract (arXiv)

For more than 20 years, the Model-RB benchmark frb100-40 remained an open challenge; since 2014, its public record had stood at 99 of 100 variables. We give a directly checkable 100-vertex independent set for its 4,000-vertex graph. Together with a verified partition into 100 cliques of size 40, the witness proves that the maximum independent-set size is 100 and the minimum vertex-cover size is 3,900. The stochastic run that found the witness is kept separate from this proof. We evaluated its added pair and triple repair operators in a preregistered campaign comprising 8,668 valid runs. The primary comparison found no detectable acceleration over base ULSA (hazard ratio 0.967, 95% confidence interval 0.915-1.023; p=0.248), and the factorial ablation reached the same conclusion. On a smaller FRB suite, the group-aware CSP pipeline solved 2,500/2,500 runs, compared with 2,391/2,500 for LibMVC-NuMVC. On frb100-40, full ULSA, base ULSA, and NuMVC each produced 0/56 new certificates. With no events, the planned cross-solver hazard ratios remain unidentified. NuMVC ended with cover size 3,902 in 40 runs and 3,903 in 16. Exhaustive enumeration showed that none of the 108 unique recorded conflict-two states had a strictly improving group-aware CSP neighbor within Hamming radius three. The certificate settles the instance. The experiments characterize the search barrier, and the preregistered comparisons show no heuristic advantage.