← Back to all news
arXiv AI By Onur U\u{g}urlu (\.Izmir Bak{\i}r\c{c}ay University)

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

Read the original on arXiv AI →

The paper presents a verified solution to the long‑standing frb100‑40 benchmark, providing a 100‑vertex independent set and a partition into 100 cliques of size 40, thereby proving the maximum independent‑set size is 100 and the minimum vertex‑cover size is 3,900. A preregistered experimental campaign of 8,668 runs evaluated new repair operators, finding no performance improvement over the baseline ULSA algorithm. Additional comparisons with other solvers (LibMVC‑NuMVC, group‑aware CSP pipeline) and exhaustive enumeration confirm the optimality certificate and characterize the search barrier for this instance.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv AI.

Related stories

arXiv AI
3d ago

Who Verifies the Graph? Misspecification Attacks on Causal Action Verification for Language Agents

The paper investigates how causal action verifiers, which guard language agents’ tool calls by checking identifiability against a committed action‑state graph, can be compromised through small graph misspecifications. By removing a single bidirected edge or reversing an arrowhead, the authors demonstrate that a verifier (CIVeX) that originally had zero false executions can suffer false execution rates up to 48.9%, with most of those executions being harmful and overall utility dropping dramatically. An additional attestation step that samples executions can detect these attacks with few false alarms, but it also leads to many wrongful rejections that reduce beneficial actions and incur significant experimental costs. whyItMatters":"The study shows that even minor errors in the verifier’s underlying graph can drastically undermine safety and performance, highlighting the need for robust auditing mechanisms."

By Fabio Rovai
agentsbenchmarkssafety
More like this →