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

The evolution of graph algorithms and combinatorial optimization over the past decades has seen significant advances, especially in problems like maximum clique, independent set, and vertex cover. Early methods such as Tomita's maximum clique algorithm, Boppana and Halldórsson's approximation algorithms, and more recent heuristic and metaheuristic approaches like ULSA and NuMVC have contributed to progress. However, large and complex instances like frb100-40, generated by the Model-RB framework, have remained unsolved due to their high structural complexity and the presence of search barriers. The instance's graph encoding includes 4,000 vertices and over half a million edges, making exhaustive search infeasible. Prior work achieved near solutions but lacked rigorous proof of optimality, leaving a gap in the theoretical understanding of such instances.

The core challenge with frb100-40 lies in its enormous search space and structural barriers that prevent heuristic algorithms from escaping local optima. Despite decades of effort, no definitive proof of the maximum independent set size existed, and the problem's complexity hindered the development of scalable verification methods. The difficulty is compounded by the instance's random construction, which creates a rugged landscape with many traps. Achieving a certifiable proof of optimality requires overcoming both computational and structural obstacles, demanding new techniques for exhaustive verification and neighborhood analysis.

This paper's key innovation is the construction of a verifiable certificate for the frb100-40 instance, explicitly demonstrating that the maximum independent set size is 100. It combines a detailed structural analysis with exhaustive enumeration within radius-3 neighborhoods, establishing the absence of improving neighbors and thus confirming the optimality. The approach leverages deterministic replay, complete enumeration, and neighborhood analysis to provide a rigorous proof, a departure from traditional heuristic methods that only approximate solutions. The introduction of radius-3 neighborhood analysis to identify search barriers is a novel contribution, offering a new perspective on the structural limitations of local search algorithms.

• �� Construct a partition of the 4,000 vertices into 100 cliques of size 40, serving as the basis for the certificate.
• �� Use the ULSA algorithm, enhanced with pair and triple repair operators, to perform large-scale stochastic local search, aiming to find the maximum independent set.
• �� Conduct exhaustive enumeration of all states within Hamming radius 3 of recorded conflict states, utilizing efficient pruning techniques to identify potential improvements.
• �� Analyze the neighborhood structure to detect the presence of search barriers, confirming that no neighboring state within radius 3 can improve the solution.
• �� Validate the certificate through deterministic replay, ensuring reproducibility and correctness.
• �� Compare different solver pipelines on smaller instances to evaluate performance differences and structural properties.

The experimental setup involved generating the frb100-40 instance using Model-RB, then applying the ULSA algorithm with various repair operators across 8,668 runs. The validation included large-scale stochastic runs, exhaustive neighborhood enumeration, and structural analysis of recorded conflict states. Additional experiments on smaller FRB instances compared the efficiency of group-aware CSP pipelines versus traditional solvers like LibMVC-NuMVC. The experiments aimed to quantify the search barriers, verify the absence of improving neighbors within radius-3, and assess the robustness of the certificate. The validation process employed deterministic replay to confirm reproducibility, with detailed logs and hashes ensuring integrity.

The primary result is the explicit certificate confirming the maximum independent set size as 100, with no improvements found within radius-3 neighborhoods. Exhaustive enumeration showed no neighboring states with fewer than two violated constraints, establishing a structural search barrier. The total search time for the successful run was significantly less than historical attempts, demonstrating the efficiency of the verification approach. On smaller instances, the group-aware CSP pipeline consistently outperformed LibMVC-NuMVC, solving all instances rapidly. The absence of new certificates on frb100-40 underscores the problem's intrinsic difficulty and the effectiveness of the structural analysis in certifying optimality.

The verification framework can be applied to other large-scale combinatorial problems, especially where structural barriers hinder heuristic search. It provides a rigorous method for certifying solutions, which is crucial in applications requiring guarantees, such as network design, resource allocation, and scheduling. The approach can inform the development of more effective global search algorithms by identifying structural obstacles. In industry, certifiable solutions enhance trustworthiness in critical systems, while in academia, they establish benchmarks for algorithmic performance and theoretical limits.

The approach relies heavily on exhaustive enumeration within radius-3 neighborhoods, which is computationally intensive and limits scalability to larger instances. The structural analysis identifies search barriers but does not provide mechanisms to overcome them, highlighting the need for fundamentally different global strategies. The verification process depends on deterministic replay, which may not be feasible for algorithms with higher randomness or adaptive behaviors. Future work should focus on scalable approximation techniques and hybrid algorithms to address these limitations.