Criticality and Parallelism in Structured SAT Instances

In this work we address the question of whether and how parallel local search exhibits the criticality and parallelism phenomenon when performed on structured instances. We experimentally show that also for structured instances there exists an optimal value of parallelism which enables the algorithm to reach the optimal performance and, by analyzing the frequency of node degree of the graphs associated with the SAT instances, we observe that an asymmetric and not regular distribution strongly affects the algorithm performance with respect to the parallelism.