In the field of automated reasoning, the development of robust SAT (Boolean Satisfiability) and CSP (Constraint Satisfaction Problem) solvers relies heavily on the availability of challenging benchmark problems. Standard random generation methods often produce instances that are either trivially easy or possess structural weaknesses that modern solvers can quickly exploit. This paper, presented at AAAI 2008, introduces a novel approach to generating "hard" instances by leveraging the properties of expander graphs and high-girth architectures.
The High-Girth Construction Algorithm
The core innovation of this research is an algorithm that constructs a problem's literal incidence graph—a bipartite graph connecting clauses to the variables they contain—while intentionally maximizing its girth (the length of the shortest cycle). Theoretical research in propositional proof complexity suggests that the hardness of a formula is intrinsically linked to the expansion properties of its underlying graph. High expansion prevents "local" contradictions, forcing solvers to explore the problem globally.
Instead of assigning variables to clauses randomly, the authors use a greedy, incremental approach:
- Initial Matching: Start with a random matching to ensure every clause has at least one variable.
- Distance Maximization: To add subsequent variables, the algorithm identifies candidate pairs of clauses and variables with low connectivity and selects the pair that is geographically farthest apart in the existing graph.
By connecting the most distant nodes, the algorithm delays cycle formation and ensures that when cycles do emerge, they are as long as possible. This high-girth structure serves as a practical proxy for high expansion, which is computationally expensive to calculate directly.
Experimental Evaluation and Results
The authors evaluated their generator across several problem types, including k-SAT (3, 4, and 5-SAT), n-ary CSPs, and XORSAT (parity-based SAT). They compared their High Girth (HG) instances against standard random baselines and "literal-balanced" methods that only ensure uniform variable frequency.
The results demonstrated that topology, rather than just balance, is the primary driver of computational hardness. As shown in the table below, HG instances consistently required significantly more time to solve than their counterparts.
Key Findings:
- 3-SAT Hardness: For instances with 350 variables, HG benchmarks took a median of 1,125 seconds to solve, whereas standard random instances were solved almost instantly.
- Scaling with Arity: The performance gap widened as the number of variables per clause ($k$) increased. For 5-SAT, HG instances were approximately three times harder than previous state-of-the-art literal-balanced methods.
- XORSAT Dominance: When applied to parity constraints (HG-$\oplus$sat), the instances became so difficult that solvers frequently timed out after 20,000 seconds, even at low variable counts.
Conclusion
This research proves that the structural girth of a problem's incidence graph is a critical factor in determining its difficulty for automated solvers. While the generation process involves higher computational overhead due to distance calculations, the resulting benchmarks provide a much more rigorous test for modern reasoning engines. Future work may focus on optimizing the generator for extremely large-scale instances and exploring the specific impacts of high-girth structures on local search solvers.
Summary updated