frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study
cs.DM · cs.AI
Quick verdict
First checkable optimality certificate for frb100-40 (α=100); preregistered search study is rigorous but finds no heuristic gain — a credible result.
Summary
This paper settles a benchmark that resisted the community for over two decades: it presents a 100-vertex independent set for the 4,000-vertex frb100-40 graph, which together with the instance's partition into 100 cliques of size 40 proves that the maximum independent set has size 100 and the minimum vertex cover has size 3,900. The certificate is printed in Appendix A and can be checked against the SHA-256-hashed public DIMACS instance. The witness came from a single stochastic ULSA+ run (695.6 billion core updates over 45.42 hours; one success among 56 processes), and the authors carefully separate this exploratory discovery from a preregistered 8,668-run campaign. That campaign found no detectable time-to-target benefit for the added pair and triple repair operators over base ULSA (hazard ratio 0.967, 95% CI 0.915–1.023, p = 0.248; the factorial ablation agrees). On a smaller FRB suite, the group-aware CSP pipeline solved 2,500/2,500 runs versus 2,391/2,500 for LibMVC-NuMVC, but solver, representation, and implementation change together, so the comparison is pipeline-level. On frb100-40 itself, all three 56-run validation arms were event-free (0/56), leaving planned cross-solver hazard ratios unidentified; NuMVC stalled at cover sizes 3,902–3,903. Exhaustive enumeration shows none of the 108 archived conflict-two states has a strictly improving grouped-CSP neighbor within Hamming radius three. Limitations include the single lucky discovery run, a Zenodo artifact not yet active, a mid-campaign protocol amendment, and the narrow scope of the landscape proposition.
Review complete
Assessment at a glance
3
risk flags identified
● high 0
● medium 2
● low 1
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- A printed 100-vertex independent set, checkable against the SHA-256-hashed public frb100-40 instance, together with its verified partition into 100 cliques of size 40, proves α(G)=100 and τ(G)=3,900.
- In the preregistered 8,668-run campaign, the pair and triple repair operators provided no detectable time-to-target advantage over base ULSA (hazard ratio 0.967, 95% CI 0.915–1.023, p=0.248), and the factorial ablation concurs.
- On the smaller FRB suite the complete group-aware CSP pipeline solved 2,500/2,500 runs versus 2,391/2,500 for LibMVC-NuMVC, a whole-pipeline comparison that does not isolate representation.
- On frb100-40 all three 56-run validation arms were event-free (0/56), so the planned cross-solver hazard ratios are unidentified; NuMVC's best covers were 3,902 (40 runs) and 3,903 (16 runs).
- Each of the 108 unique archived conflict-two terminal states admits no strictly improving grouped-CSP move within Hamming radius three (Proposition 2, computer-assisted, recorded-state scope).
Strengths
The central result is mechanically checkable by anyone
Appendix A prints all 100 certificate vertices; combined with the instance's structural partition into 100 cliques of size 40 (Section III-A), optimality (α=100, τ=3900) reduces to scanning 572,774 edges against a public BHOSLIB DIMACS file fixed by SHA-256. Edge bookkeeping is internally consistent: 78,000 intra-group = 100·C(40,2) plus 494,774 cross-group.
Exemplary discovery/proof separation
The witness came from one of 56 exploratory processes (task 33, seed 164415777); the paper consistently labels that cohort exploratory and grounds the headline claim only in the checkable witness, not in the 1/56 discovery rate. This discipline is stated in Sections I, III-C and VI.
Preregistered reporting of a null result about the authors' own operators
Deep verification stack
Honest handling of zero-event outcomes
Weaknesses
The heuristic contribution is effectively negative
Artifact not yet inspectable
Protocol deviation mid-campaign
A1 pipeline comparison is confounded by design
Proposition 2 has very narrow scope
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper makes two cleanly separated contributions. First, an **optimality certificate** for frb100-40, the largest BHOSLIB Model-RB instance (4,000 vertices, 572,774 edges; record stuck at 99/100 since Rosin 2014): Appendix A prints 100 one-based DIMACS vertices that form an independent set, and since the instance's first 40-vertex blocks are cliques partitioning the vertex set, α(G) ≤ 100 follows structurally and the witness forces α(G) = 100; the complement gives τ(G) = 3,900. The instance is pinned by SHA-256, and the edge bookkeeping (78,000 intra-group = 100·C(40,2); 494,774 cross-group) is internally consistent. Second, a **preregistered search study** (8,668 valid runs) that asks whether the pair/triple repair operators used in the discovery actually help — and answers no (Table II: H1 hazard ratio 0.967, 95% CI 0.915–1.023, Holm p = 0.743). The priority claim is deliberately hedged ("first publicly checkable size-100 assignment known to us"), which is the right posture. Claims and evidence are well matched throughout; nothing in the text overreaches the data.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 3 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is frb100-40 and why does it matter?
frb100-40 is a hard random constraint-satisfaction instance from Model RB (100 variables, domain size 40) whose graph encoding has 4,000 vertices and 572,774 edges. Distributed with the BHOSLIB benchmark suite, it has been a standard stress test for maximum clique, maximum independent set, and minimum vertex cover solvers. Since 2014 the best publicly known solution covered 99 of 100 variables; this paper proves that 100 is optimal.
How can I verify the paper's optimality claim myself?
Download the public frb100-40 DIMACS instance (the paper pins it with a SHA-256 hash), take the 100 vertex indices listed in Appendix A, and run two cheap checks: each block of 40 consecutive vertices contributes exactly one selected vertex, and no edge of the graph has both endpoints selected. Because the graph partitions into 100 cliques of size 40, no independent set can exceed 100, so the listed set is a full optimality proof; the complement is a minimum vertex cover of 3,900.
Did the paper's new search heuristic beat existing methods?
No. The preregistered comparisons found no detectable speedup of the proposed pair/triple repair operators over base ULSA (hazard ratio 0.967, p=0.248), and on frb100-40 none of three solvers found a certificate in 56 runs each. The contribution is the certificate itself, not the heuristic. The group-aware pipeline did outperform LibMVC-NuMVC on smaller FRB instances (2,500/2,500 vs 2,391/2,500), but that comparison changes solver, representation, and implementation together.
What is the minimum vertex cover size of frb100-40?
3,900. The graph has 4,000 vertices, and since the maximum independent set is 100 vertices, the complement of any maximum independent set is a vertex cover of 4,000 − 100 = 3,900 vertices, which is therefore minimum. The paper's NuMVC baseline stalled at covers of 3,902–3,903.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1–4 are present in the extraction only as axis tick labels and captions; the plotted curves themselves could not be reviewed, so figure-level judgments rely on the in-text tables and numbers.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.