Correlating the Community Structure of Constraint Satisfaction Problems with Search Time

Michel Medema*, Alexander Lazovik*

*Bijbehorende auteur voor dit werk

OnderzoeksoutputAcademicpeer review


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.
Originele taal-2English
TijdschriftInternational Journal on Artificial Intelligence Tools
Nummer van het tijdschrift7
StatusPublished - 18-nov.-2022


Duik in de onderzoeksthema's van 'Correlating the Community Structure of Constraint Satisfaction Problems with Search Time'. Samen vormen ze een unieke vingerafdruk.

Citeer dit