frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study
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…
We haven't written up this one. arXiv cs.AI has the full story — the link below goes straight to it.
