Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper resolves the long-standing challenge of the frb100-40 benchmark by providing a checkable independent set of 100 vertices for its 4,000-vertex graph, alongside a verified partition into 100 cliques of size 40. The results confirm that the maximum independent-set size is 100 and the minimum vertex-cover size is 3,900, effectively settling the instance after two decades of uncertainty. Additionally, a comprehensive evaluation of various search strategies revealed no significant acceleration over the base ULSA method, indicating the robustness of the search barrier in this context.
After two decades, a definitive independent set for the frb100-40 benchmark proves its maximum independent-set size is 100, but no search strategy offers a heuristic advantage.
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.