Original title: frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study
Onur Uğurlu · September 2026
For over 20 years, a hard benchmark math problem called frb100-40 stood unsolved. Researchers wanted to find the largest group of connected points, or vertices, on a 4,000-vertex graph that share no links with one another. This is called an independent set. The previous public record stopped at 99 points out of 100. In this paper, researchers provide a directly checkable solution that hits all 100 points. They paired this with a verified split of the graph into 100 tightly connected groups of size 40. This proves the largest possible independent set really is 100, which also fixes the smallest vertex cover at 3,900 points. Although the team found the winning answer using a randomized search with extra repair steps, testing those new steps across thousands of runs showed they did not actually speed up the base search tool.
Imagine organizing a team for a project where certain people cannot work together due to conflicts. You want the largest team possible with no internal conflicts. The connections are so tangled that it's hard to find the best team. Here, the researchers tackled a similar puzzle with 4,000 people and proved that the largest conflict-free team has exactly 100 members.
This closes a benchmark problem that has stumped computer algorithms for decades. It helps researchers understand why some puzzles are so hard to solve and can improve future algorithm design.
The work only solves the specific frb100-40 benchmark and doesn't address other problems. The new repair operators tested did not outperform existing methods. Some planned statistical analyses couldn't be completed due to no events in the data.
Ask anything about this paper. Answers come from its abstract, and say so when the abstract doesn't cover your question.
frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study — Onur Uğurlu
Abstract licence: CC0
Explanation generated by Synthesis from the abstract — it is not the original paper. This is a preprint, so it hasn't necessarily been peer reviewed.