Correlating the Community Structure of Constraint Satisfaction Problems with Search Time

A constraint satisfaction problem (CSP) is, in its most general form, an NP-complete problem. One of the several classes of tractable problems that exist contains all the problems with a restricted structure of the constraint scopes. This paper studies community structure, a particular type of restricted structure underpinning a class of tractable SAT problems with potentially similar relevance to CSPs. Using the modularity, it explores the community structure of a wide variety of problems with both academic and industrial relevance. Its impact on the search times of several general solvers, as well as one that uses tree-decomposition, is also analysed to determine whether constraint solvers exploit this type of structure. Nearly all CSP instances have a strong community structure, and those belonging to the same class have comparable modularity values. For the general solvers, strong correlations between the community structure and the search times are not apparent. A more definite correlation exists between the modularity and the search times of the tree-decomposition, suggesting that it might, in part, be able to take advantage of the community structure. However, combined with the relatively strong correlation between the modularity and the tree-width, it could also indicate a similarity between these two measures.

Automated summary

This paper studies the community structure in CSPs and finds that almost all instances have a strong community structure, with comparable modularity values for instances in the same class. However, the correlation between community structure and search times in general solvers is not strong, while there is a more definite correlation with search times in tree-decomposition. This suggests that tree-decomposition may partially utilize the community structure, along with a relatively strong correlation between modularity and tree-width indicating a potential similarity between these measures.