frb100-40: Settling a 20-Year Benchmark, and Reporting the Null Result Honestly

Paper: 2609.02804 Author: Onur Uğurlu Categories: cs.DM, cs.AI

The Gap

The Model-RB benchmark instance frb100-40 had been an open challenge for more than twenty years, and since 2014 its public record stood at 99 of 100 variables. A single variable in a 4,000-vertex graph had resisted two decades of search — which is exactly the kind of gap that accumulates folklore, since nobody can tell whether the last variable is hard or whether the heuristics have simply not been lucky.

Two things were missing, and they are different in kind. First, a proof: a search result of 100 is only as good as the record of it, and a witness that others can check is what turns “we found 100” into a settled fact. Second, an honest account of whether the method that found it is actually better than what came before — because a method credited with cracking a long-standing instance will be adopted, and if its advantage is luck, that adoption is a mistake.

   frb100-40: A LONG-STANDING OPEN INSTANCE

   Model-RB benchmark, 4,000-vertex graph
     open challenge for MORE THAN TWENTY YEARS
     public record since 2014: 99 of 100 variables
        |
        v
   ONE variable resisted two decades of search
        -> exactly the kind of gap where FOLKLORE accumulates
        -> nobody can tell whether the last variable is
           HARD or the heuristics have just not been LUCKY
        |
        v
   TWO THINGS MISSING, DIFFERENT IN KIND
     [1] A PROOF: a result of 100 is only as good as its record;
         a CHECKABLE WITNESS turns "we found 100" into a fact
     [2] AN HONEST ACCOUNT of whether the method that found it
         is ACTUALLY BETTER -- because a method credited with
         cracking a long-standing instance gets ADOPTED, and if
         its advantage is luck, that adoption is a mistake

The Increment

One sentence: Before this paper, frb100-40’s record stood at 99 and the method that reached 100 would have been credited on the strength of one success; after it, a checkable certificate settles the instance and a preregistered campaign of 8,668 runs shows no detectable heuristic advantage.

Core Mechanism

The result comes in two parts, and the paper is careful to keep them apart — which is the paper’s methodological contribution.

Part one: the certificate. The authors give a directly checkable 100-vertex independent set for the 4,000-vertex graph. Together with a verified partition into 100 cliques of size 40, that witness proves the maximum independent-set size is 100 and the minimum vertex-cover size is 3,900. The certificate is self-contained: anyone can verify the two objects and check the arithmetic, without trusting the search or reproducing it. The proof structure is worth noting — an independent set of size 100 establishes a lower bound, the clique partition establishes an upper bound, and together they pin the value exactly.

And the paper’s discipline shows in how it handles the search. The stochastic run that found the witness is kept separate from this proof. That separation is the whole reason the result is settled: a heuristic success is evidence about the heuristic, never a proof about the graph, and conflating them is the standard way a reported record becomes unreproducible.

Part two: the preregistered campaign. The added pair and triple repair operators were evaluated in a preregistered campaign of 8,668 valid runs. Preregistration is the right instrument here, and it is what makes the negative result trustworthy: the hypothesis, the comparison and the analysis were fixed before the runs, so the conclusion cannot be an artefact of choosing the flattering test afterwards.

The primary comparison found no detectable acceleration over base ULSA — hazard ratio 0.967, 95% confidence interval 0.915 to 1.023, p=0.248 — and the factorial ablation reached the same conclusion. Reporting a hazard ratio with an interval spanning 1 is a precise way of saying “no detectable effect”, and it is the opposite of the framing one would expect from a paper with a 20-year record on its first page.

The remaining results characterise the search barrier rather than claiming an advance:

• On a smaller FRB suite, the group-aware CSP pipeline solved 2,500 of 2,500 runs, against 2,391 of 2,500 for LibMVC-NuMVC — a genuine positive result on the easier instance class.
• On frb100-40 itself, full ULSA, base ULSA and NuMVC each produced 0 of 56 new certificates. With no events, the planned cross-solver hazard ratios remain unidentified — an honest statement that the comparison could not be made, rather than a claim of equivalence.
• NuMVC ended with cover size 3,902 in 40 runs and 3,903 in 16 — so successors came close without closing.
• Exhaustive enumeration showed that none of the 108 unique recorded conflict-two states had a strictly improving group-aware CSP neighbour within Hamming radius three. That is a local optimality result, and it explains the barrier: no small step from any state reached improves the objective.

   PART ONE: THE CERTIFICATE

   a DIRECTLY CHECKABLE 100-vertex independent set
     (for the 4,000-vertex graph)
   + a VERIFIED partition into 100 cliques of size 40
        |
        v
   independent set of 100 -> establishes a LOWER bound
   clique partition       -> establishes an UPPER bound
        |
        v
   PROVES: max independent-set size = 100
           min vertex-cover size     = 3,900
   -> self-contained: anyone can verify without trusting or
      reproducing the search

   DISCIPLINE: the STOCHASTIC RUN that found the witness is
   kept SEPARATE from the proof
     <- a heuristic success is evidence about the HEURISTIC,
        never a proof about the GRAPH
     <- conflating them is how a reported record becomes
        unreproducible

   PART TWO: THE PREREGISTERED CAMPAIGN
     added PAIR and TRIPLE repair operators evaluated in a
     PREREGISTERED campaign of 8,668 valid runs
     <- hypothesis, comparison and analysis fixed BEFORE the runs
        -> the negative result cannot be an artefact of choosing
           the flattering test afterwards
        |
        v
     PRIMARY comparison: NO DETECTABLE ACCELERATION over base ULSA
       hazard ratio 0.967, 95% CI 0.915-1.023, p = 0.248
       factorial ablation: SAME conclusion
        |
        v
   OTHER RESULTS (characterising the barrier, not claiming a win)
     smaller FRB suite: group-aware CSP 2,500/2,500
                        vs LibMVC-NuMVC 2,391/2,500
     on frb100-40 itself: full ULSA, base ULSA, NuMVC
                        each 0/56 new certificates
       -> no events -> planned cross-solver hazard ratios
          REMAIN UNIDENTIFIED (not "equivalent")
     NuMVC ended at cover size 3,902 (40 runs), 3,903 (16)
     EXHAUSTIVE enumeration: none of the 108 unique recorded
       conflict-two states had a strictly improving group-aware
       CSP neighbour within Hamming radius three
       -> local optimality, explaining the barrier

Think of it as a mountaineering team that summits, publishes the survey data, and then reports that their new boots made no difference. The summit claim is settled because they publish the coordinates and the route — anyone can check the summit exists and the route works, without re-doing the climb. Separately, they ran a controlled comparison of the boots they credited and found no significant advantage over their old ones. The temptation in that situation is enormous: you have the summit, so you attribute it to the equipment and say so. Declining to — and preregistering the comparison so the decline is credible — is what makes the rest of the report worth reading.

Key Concepts

• A checkable certificate versus a search result: an independent set plus a clique partition pins the optimum exactly, and the witness is verifiable without reproducing the search. A search result, however strong, is a statement about the method.
• Keeping the stochastic run separate from the proof: the discipline that makes the record settled. Heuristic success and mathematical proof are different claims, and only the second survives the discoverer’s method being wrong.
• Preregistration as the instrument for a negative result: fixing the hypothesis, comparison and analysis before the runs. Without it, “no advantage” is indistinguishable from “we looked until we found nothing”.
• Unidentified versus equivalent: with zero events on frb100-40, the planned cross-solver comparisons cannot be estimated. Saying so, rather than reporting equivalence, is the precise form of the claim.
• Local optimality as the barrier’s explanation: no conflict-two state reached has a strictly improving neighbour within Hamming radius three. It explains why two decades of progress stopped, rather than only reporting that it did.

Framework Shift

Before (a record, and a method credited with it):
  public record: 99 of 100 variables since 2014
  -> search result treated as the finding
  -> whatever found the last variable gets adopted
  -> no way to tell whether the method helped or got lucky

After (a certificate, and an honest null):
  checkable certificate proves optimum = 100
    (independent set + clique partition; search kept separate)
  already-reported heuristic advantage
    -> preregistered 8,668-run campaign
    -> hazard ratio 0.967 [0.915, 1.023], p = 0.248
    -> no detectable acceleration; factorial ablation agrees
  barrier explained by exhaustive local enumeration

From a long-standing record whose cracking would have been credited to a heuristic, to a settled optimum with the heuristic’s advantage honestly tested and found absent, the core shift is that proving the instance and evaluating the method are separate acts, and only the first can be settled by a witness.

Expert Assessment

Problem choice: Excellent, and the combination is unusual. Settling a twenty-year benchmark and reporting that the method responsible shows no measurable advantage are two contributions that normally appear in different papers, and juxtaposing them here produces something rarer than either: a result that is both conclusive about the instance and honest about the method.

Method maturity: The certificate construction is clean — lower bound from the independent set, upper bound from the clique partition, value pinned exactly, witness directly checkable. Preregistering the heuristic comparison is the more sophisticated decision, because it is precisely the comparison the author had the most incentive to find favourable, having found the witness with those operators. Reporting the factorial ablation agreeing with the primary comparison is the right corroboration.

Experimental integrity: This is the paper’s strongest dimension undiminished by its scope being a single instance. The 8,668-run preregistered campaign, the explicit hazard ratio with a confidence interval spanning 1, the “0 of 56” event counts, the refusal to report equivalence from unidentified quantities, and the separate positive result on the smaller suite all point the same way. The honest limitation is that one benchmark instance and one hardware/software setting cannot speak to whether the repair operators help elsewhere, and the paper’s conclusion is scoped to “the search barrier” of this instance.

Writing quality: The abstract separates the proof from the experiments in the first two sentences, which is exactly the right ordering for a paper with a certificate to publish. Because the practical reader may want to reuse the operators, a short statement distinguishing “no advantage on frb100-40” from “no advantage in general” would help them decide — the paper implies the distinction but a reader moving quickly could miss it.

Verdict: strong accept — it settles a twenty-year open instance with a checkable certificate, and it reports the null result for the method that found it under preregistration, which is a standard the field should adopt more widely.

Takeaways

• Publish a checkable witness, not just a search result. A certificate anyone can verify settles the claim; a heuristic success only describes the heuristic.
• Keep the run that found the answer separate from the proof of it. Conflating the two is how results become unreproducible when the method turns out to be unreliable.
• Preregister before evaluating something you already believe in. It is what makes a null result about your own method credible.
• Distinguish unidentified from equivalent. When there are no events, the honest report is that the comparison could not be made.