Source-linked AI summary
frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study
Onur Uğurlu
TL;DR
The paper addresses the long-standing frb100-40 challenge by providing a directly checkable independent-set certificate and separately evaluating the search operators that found it. The certificate settles the hashed instance, while preregistered experiments found no heuristic advantage from pair and triple repairs and exposed a finite local-search barrier.
Problem
frb100-40 had remained an open benchmark challenge, with the public record at 99 of 100 variables since 2014.
Method
The paper combines a directly checkable independent-set witness and verified clique partition with a preregistered 8,668-run evaluation of pair and triple repairs, smaller-instance comparisons, and structural audits.
Results
The certificate proves α(G) = 100 and τ(G) = 3900, while the preregistered comparisons found no speed advantage for the repairs and no new certificates in the frb100-40 validation arms.
Takeaways & Limitations
The hashed instance is settled independently of discovery, and future methods should look beyond the audited radius-three neighborhood or deliberately allow neutral and worsening steps.
Takeaways & Limitations
The all-censored 0/56 validation arms leave planned cross-arm hazard ratios unidentified, and the radius-three proposition applies only to 108 archived states and the audited neighborhood.
Abstract
from arXiv · showhide
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.
I. INTRODUCTION
frb100-40 was a longstanding 99-of-100 challenge, and the paper provides a checkable 100-vertex certificate establishing optimality while separately evaluating the search process.
- frb100-40 is a 100-variable, domain-size-40 benchmark whose public record stood at 99 satisfied variables.
- The paper reports a first publicly checkable size-100 assignment known to the authors for this described 20-year challenge.
- The certificate combines one vertex from each group, no internal edges, and a verified 100-clique partition to establish α(G) = 100 and τ(G) = 3900.
- A preregistered 8,668-run campaign tested periodic pair and triple repairs separately from the witness proof and found no speed advantage over base ULSA.
- Enumeration around 108 conflict-two assignments found no strictly improving grouped-CSP neighbor within Hamming radius three, identifying a finite search barrier.
B. Stochastic Local Search for CSP and Vertex Cover
The paper situates ULSA within stochastic local search and contrasts its group-aware CSP state space with general-graph vertex-cover methods and larger-neighborhood search.
- Stochastic local search combines improving steps with plateau traversal or escape mechanisms for local minima.
- ULSA is an unweighted, group-aware CSP method that updates one endpoint of a violated constraint using scores, recency, and randomized tie breaking.
- NuMVC and related MinVC methods use a different general-graph state space with exchanges, edge weighting, configuration checking, or forgetting.
- Prior work on two- and three-vertex exchanges, reductions, exact algorithms, and exhaustive k-swap search motivates the paper’s repairs and radius-three enumeration.
A. A Checkable Proof of Optimality
A directly auditable witness and clique partition certify the hashed graph’s optimum, while ULSA+ adds periodic strict-improvement pair and triple operators for search.
- A. A Checkable Proof of Optimality: Direct enumeration verifies 100 disjoint 40-vertex groups, each inducing K40, supporting a certifying proof independent of the producing program.
- A. A Checkable Proof of Optimality: α(G) = 100 and τ(G) = 3900 for the hashed graph, proved by the 100-vertex edge-free witness, clique upper bound, and α(G) + τ(G) = |V|.
- B. ULSA+: ULSA+ leaves ULSA’s core update unchanged and adds two periodic strict-improvement operators.
- B. ULSA+: Every 2^9 core updates, the pair operator evaluates d^2 joint assignments and accepts only assignments that strictly reduce violations.
- B. ULSA+: Every 2^18 updates, the triple operator evaluates d^3 assignments with safe lower-bound pruning and accepts only strict improvements.
C. Discovery Run and Deterministic Replay
The discovery campaign found one certificate-producing run, and a same-seed replay reproduced its output while the preregistered campaign used frozen, separated evaluation blocks.
- C. Discovery Run and Deterministic Replay: One of 56 exploratory ULSA+ processes reached zero violations after 695,602,633,182 core updates and produced the certificate.The other 55 processes ended their budgets without a certificate.
- C. Discovery Run and Deterministic Replay: The production-source replay with the same seed was byte-identical to the archived reference, establishing deterministic same-seed reproducibility.Independent stochastic replication would require new seeds.
- C. Discovery Run and Deterministic Replay: The manifest and analysis plan were frozen before validation results were inspected, while the discovery cohort remained exploratory.
- C. Discovery Run and Deterministic Replay: A1 comprised five instances from each family frb30-15 through frb59-26, while A2 used four remaining instances with 25 seeds per factorial cell.
- C. Discovery Run and Deterministic Replay: Experiments ran as one-core processes with hashed source, binary, manifest, preregistration, instance, and dispatcher materials to prevent build mixing.
B. Preregistered Outcomes and Analysis
The preregistered analysis specified stratified survival models for the primary comparison and factorial repair ablation, while treating the NuMVC comparison as descriptive.
- Primary analysis: The primary hypothesis compared full ULSA+ and base ULSA using an instance-stratified Cox model with clustered seed-block covariance.RMST at the family cutoff was the principal effect size; because every A1 CSP run succeeded, it equals the observed mean time.
- Factorial ablation: The A2 factorial model tested pair, triple, and pair-by-triple effects with stratified Cox regression and clustered logistic regression for success.All 800 validation observations succeeded, leaving the success model unidentifiable.
- Multiple testing and uncertainty: The analysis plan grouped H1, the A2 pair effect, and the pair-by-triple interaction into a three-test Holm family.Success-rate intervals used exact Clopper–Pearson intervals, while RMST uncertainty used a fixed-seed, 10,000-repetition two-stage bootstrap.
- Cross-solver comparison: The NuMVC comparison was descriptive and evaluated complete operational pipelines rather than isolating representation, algorithm, or implementation effects.NuMVC medians were computed among successful runs and displayed with success rates.
A. Certificate and Corpus Verification
The corpus and certificates were independently checked, while discovery and validation evidence were kept separate. The preregistered results found no supported acceleration from the repair operators.
- Certificate and artifact checks: The parser confirmed 4,000 vertices, 100 complete 40-cliques, 100 unique certificate vertices, and zero selected conflict edges.The replay output was also byte-identical to its frozen reference.
- Validation corpus: 8,668 frozen validation runs were completed, and all 8,391 emitted success flags were rechecked by an independent C verifier.No unverified success was included.
- Discovery versus validation: The successful discovery seed came from an earlier exploratory cohort and was excluded from the validation event count.Its same-seed replay establishes deterministic reproducibility, while independently seeded runs provide the stochastic evidence.
- Preregistered outcomes: The primary Cox comparison found no support for H1: full ULSA+ versus base ULSA had hazard ratio 0.967 (95% CI 0.915–1.023; raw p = 0.248; Holm-adjusted p = 0.743).RMST was 2.540 s for full and 2.283 s for base, a difference of 0.257 s with bootstrap 95% CI −0.367 to 1.134 s.
- Factorial ablation: The A2 stratified model found no evidence that pair, triple, or interaction differences represented repair effects.All 1,000 A2 runs attributed the final successful transition to ULSA’s core update, not a pair or triple repair.
C. Pipeline Performance on the Smaller FRB Suite
On the smaller FRB suite, the group-aware CSP pipeline was more reliable than LibMVC-NuMVC, but the comparison remains descriptive because the operational pipelines differ in several components.
- Suite-level results: 2,500/2,500 full ULSA+ runs were verified solutions, compared with 2,391/2,500 for LibMVC-NuMVC.The corresponding success rates were 100% and 95.64%, respectively.
- Practical interpretation: The smaller-suite difference matters for practitioners starting from original CSP groups because the group-aware pipeline was more reliable and reached targets sooner.The comparison covers complete operational pipelines.
- Terminal objective quality: NuMVC ended with cover size 3,902 in 40 runs and 3,903 in 16, corresponding to objective gaps of +2 and +3 from the certified optimum.It never reported the target within or after the scientific budget.
- Post-hoc comparison: Post-hoc conversion of C and B1 assignments produced independent sets of size 99 for five records and 98 for the remaining 107.The reconstructed C and B1 values and native NuMVC objectives had suggestive visual agreement at +2, but simultaneous solver changes preclude confirmatory cross-solver interpretation.
E. Radius-Three Structure of the Recorded Endpoints
The audited conflict-two endpoints were exhaustively tested and showed no strictly improving grouped-CSP neighbor within Hamming radius three. Acceptance and endpoint-distance analyses add structural context, while the validation arms remained certificate-free.
- Radius-three audit: 108 unique conflict-two assignments had no strictly improving grouped-CSP neighbor within Hamming radius three.The proposition applies to the recorded states and audited neighborhood only.
- Radius-three audit: 887,040,000 pair assignments and 133,442,560,000 remaining triple assignments were exhaustively evaluated without improving on two violations.A second implementation reproduced both counts and the zero-improvement result.
- Scope: The audited proposition excludes equal-cost, worsening, and larger-radius moves, which remain possible.The successful discovery trajectory ultimately escaped this objective level.
- Endpoint geometry: 112 conflict-two records had mean Hamming distance 95.991 from the particular optimum certificate, with a range of 89–100.Distance to the nearest optimum remains unknown because other optima may exist.
- Validation context: Each validation arm produced 0/56 verified certificates, leaving the planned hazard ratios unidentified.The endpoint-gap figure reports exact two-sided 95% confidence intervals of 0–6.38%.
VI. DISCUSSION
The discussion separates the unconditional certificate from exploratory search evidence and interprets the experiments cautiously. It identifies a finite local-search barrier while emphasizing limitations in causal attribution, sampling, and validation power.
- Certificate and search: The certificate is unconditional for the hashed input because its vertices and clique cover are independently checkable.This separates the proof from the low empirical discovery rate.
- Certificate and search: Pair and triple repairs showed no detectable time-to-target gain over base ULSA across the preregistered campaign.The evidence supports interpreting the certificate as arising from a rare trajectory generated by a reproducible search system.
- Search barrier: At recorded conflict-two endpoints, escaping by strict improvement requires changing at least four variables or first accepting equal or higher conflict.This exact statement holds for the archived states.
- Interpretive limits: The smaller-suite pipeline comparison changes solver, state space, and implementation together, so its performance advantage cannot identify a causal encoding effect.The result informs pipeline selection, while causal attribution requires a controlled design.
- Interpretive limits: The successful seed came from an exploratory cohort, and all validation arms observed 0/56 successes, leaving hazard ratios unidentified.The same-seed replay contributes deterministic evidence rather than a preregistered discovery-rate estimate.
- Interpretive limits: The radius-three proposition covers 108 dependent archived states and the audited neighborhood, not the broader search space.The landscape analyses were designed after the main campaign and remain exploratory.
- Interpretive limits: C and B1 ran in different calendar blocks after a dispatcher/preregistration amendment, leaving node and calendar effects possible.Solver source and binaries were unchanged.
VII. CONCLUSION
The paper settles the hashed frb100-40 instance with an independently checkable certificate and reports a mixed search-study outcome. The structural audit identifies a finite barrier, while the reproducibility artifact supports verification and reuse.
- Conclusion: α(G) = 100 and τ(G) = 3900 follow from the 100-vertex independent set and matching 100-clique partition.These equalities are independent of how the witness was found.
- Conclusion: Across 8,668 completed preregistered runs, pair and triple repairs gave no detectable improvement over base ULSA.The smaller-suite group-aware CSP pipeline performed better than LibMVC-NuMVC, with solver, representation, and implementation varying together.
- Conclusion: All three frb100-40 validation arms were event-free, and 108 archived conflict-two states lacked strictly improving grouped-CSP moves within radius three.Methods should therefore examine larger neighborhoods or deliberately allow neutral and worsening steps.
- Conclusion: The reproducibility artifact contains the hashed graph, certificate, verifiers, logs, manifests, scripts, raw campaign records, and build receipts.It was deposited at Zenodo under the reserved DOI 10.5281/zenodo.22257064.