MathDB

Model-RB frb100-40 maximum-independent-set challenge

Let Gfrb100-40=(V,E)G_{\mathrm{frb100\text{-}40}}=(V,E) be the publicly specified 4,0004{,}000-vertex Model-RB benchmark graph. Determine its independence number α(Gfrb100-40)\alpha(G_{\mathrm{frb100\text{-}40}}), equivalently find a set S⊆VS\subseteq V of maximum cardinality such that for all distinct u,v∈Su,v\in S, {u,v}∉E\{u,v\}\notin E. The reported certificate claims that α(Gfrb100-40)=100\alpha(G_{\mathrm{frb100\text{-}40}})=100.

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Minimum vertex-cover formulation

    For the same graph Gfrb100-40G_{\mathrm{frb100\text{-}40}}, determine the minimum cardinality of a vertex cover; the reported certificate claims that this minimum is 3,9003{,}900, equivalently τ(Gfrb100-40)=3,900\tau(G_{\mathrm{frb100\text{-}40}})=3{,}900.

    source: frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study

References

Primary source

arXiv

Additional references

combinatoricscomputational-mathematicsgraph-algorithms
Posted

Progress summary

Refreshed
Claimed solved

A newly reported certificate claims the long-running benchmark is solved at size 100, but no independent verification was found.

The challenge asks for the maximum independent set in the Model-RB benchmark instance frb100-40, a planted random instance made available online in 2005. It had remained unsolved despite a best reported value of 9999 out of 100100.

Known results

  • ULSA reached 9999 of 100100 variables in 1616 runs, but did not solve the instance (2014).
  • Earlier methods reportedly reached at most 9898 in the corresponding maximum-independent-set formulation (2014).
  • The benchmark was still described as unsolved in 2023.

September 2, 2026 certificate claim

A report dated September 2, 2026 says that frb100-40 After Two Decades: An Optimality Certificate and a Preregistered Search Study gives a 100100-vertex independent-set witness and partitions the 4,0004{,}000-vertex graph into 100100 cliques of size 4040, which would prove optimality. The claim is not independently verified in the retrieved sources.

en.wikipedia.org · deepmind.google · openai.com · par.nsf.gov · github.com · quera.com · mathoverflow.net · queracomputing.github.io · arxiv.org · arxiv.org · ar5iv.labs.arxiv.org · mathstodon.xyz · mathstodon.xyz · mathstodon.xyz · mathstodon.xyz · openai.com · openai.com · cdn.openai.com · cdn.openai.com · quantamagazine.org · openai.com

Current status (as of September 2026): The benchmark is claimed solved with optimum 100100, but that certificate has not been independently verified; the earlier established record was 9999.

Sources

Solutions 0

No solutions have been posted yet.