Introduction
The Boolean Satisfiability Problem (SAT) is a cornerstone of computational complexity. While modern Conflict-Driven Clause Learning (CDCL) solvers handle massive industrial instances efficiently, they often struggle with much smaller, purely random formulas. This performance gap is largely attributed to the internal structure of real-world problems, specifically modularity—the tendency of variables to form tightly knit communities. To bridge this gap, we introduce the Community Attachment (CA) model, a random SAT generator that allows for the creation of synthetic benchmarks with precisely controllable modularity.
The Community Attachment (CA) Model
The CA model mimics industrial structure by partitioning $n$ variables into $c$ communities. When generating $m$ clauses, the model uses a probability parameter $P$ to determine variable selection:
- Intra-community clauses (with probability $P$): Variables are selected from the same community.
- Inter-community clauses (with probability $1-P$): Variables are selected from distinct communities.
This mechanism allows for a predictable expected modularity $E[Q] \approx P - 1/c$, enabling the generation of instances ranging from unstructured ($Q \approx 0$) to highly modular ($Q > 0.7$), typical of industrial benchmarks.
Structural Stability and Control
A key requirement for a synthetic generator is the ability to maintain target structural properties across different problem scales. As shown in Figure 1, the CA model successfully produces instances where both the modularity $Q$ and the number of communities $c$ remain stable as the number of variables $n$ increases. Furthermore, the model's behavior is consistent across different clause densities ($m/n$); while the number of detected communities naturally decreases as the formula becomes denser and components merge, the modularity $Q$ stabilizes quickly, providing a reliable benchmark for solver evaluation.
Solver Specialization and Performance
Our research confirms that modularity is one of the best predictors of CDCL solver performance. High modularity makes a problem "easier" because solvers can focus their search on one community at a time. Visual analysis of variable decisions shows that CDCL solvers naturally "cluster" their work, solving one community almost entirely before moving to the next. This leads to a clear specialization: as modularity increases, industrial-specialized solvers like Glucose become significantly faster, while random-specialized solvers like March struggle or fail.
Despite these structural variations, the characteristic "phase transition" of random SAT—the specific clause-to-variable ratio where problems become suddenly very hard—remains stable. For 3-SAT, this hard-to-solve region persists near the classical ratio of $\approx 4.26$ regardless of the modularity level, proving that community structure does not fundamentally shift the satisfiability threshold.
Conclusion
The Community Attachment model provides a robust framework for generating pseudo-industrial SAT instances. By controlling modularity, researchers can better understand the structural features that make industrial problems tractable and develop more efficient solvers. Future work will focus on incorporating hierarchical modularity and non-uniform community sizes to further enhance the realism of synthetic benchmarks.
Summary updated