TitleThe Community Structure of SAT Formulas
Publication TypeConference Paper
Year of Publication2012
AuthorsAnsótegui C, Giráldez-Cru J, Levy J
EditorCimatti A, Sebastiani R
Conference NameProc. of the 15th Int. Conf. on Theory and Applications of Satisfiability Testing, SAT'12
Conference LocationTrento, Italy
Date Published17/06/2012

The research community on complex networks has developed techniques of analysis and algorithms that can be used by the SAT community to improve our knowledge about the structure of industrial SAT instances. It is often argued that modern SAT solvers are able to exploit this hidden structure, without a precise definition of this notion. In this paper, we show that most industrial SAT instances have a high modularity that is not present in random instances. We also show that successful techniques, like learning, (indirectly) take into account this community structure. Our experimental study reveal that most learnt clauses are local on one of those modules or communities.