TítuloOn the Modularity of Industrial SAT Instances
Publication TypeConference Paper
Year of Publication2011
AuthorsAnsótegui C, Levy J
EditorFernandez C, Geffner H, Manyà F
Conference NameProc. of the 14th Int. Conf. of the ACIA, CCIA'11
Volume232
EditorialIOS Press
Conference LocationLleida, Spain
Paginación11-20
Date Published26/10/2011
Palabras claveSAT
Resumen

Learning, re-starting and other techniques of modern SAT solvers have been shown efficient when solving SAT instances from industrial application. The ability to exploit the structure of these instances has been proposed as the responsible of such success. Here we study the modularity of some of these instances, used in the latest SAT competitions. Using a simple label propagation algorithm we show that the community structure of most of these SAT instances can be identified very efficiently. We also discuss how this structure may be used to speed up SAT solvers.