Title
Colouring, constraint satisfaction, and complexity
Abstract
Constraint satisfaction problems have enjoyed much attention since the early seventies, and in the last decade have become also a focus of attention amongst theoreticians. Graph colourings are a special class of constraint satisfaction problems; they offer a microcosm of many of the considerations that occur in constraint satisfaction. From the point of view of theory, they are well known to exhibit a dichotomy of complexity — the k-colouring problem is polynomial-time solvable when k≤2, and NP-complete when k≥3. Similar dichotomy has been proved for the class of graph homomorphism problems, which are intermediate problems between graph colouring and constraint satisfaction. However, for general constraint satisfaction problems, dichotomy has only been conjectured. Although the conjecture remains unproven to this day, it has been driving much of the theoretical research on constraint satisfaction problems, which combines methods of logic, universal algebra, analysis, and combinatorics. Currently, this is a very active area of research, and it is our goal here to present some of the recent developments, updating some of the information in existing books and surveys, while focusing on both the mathematical and the computational aspects of the theory. Given the level of activity, we are only able to survey a fraction of the new work, with emphasis on our own areas of interest.
Year
DOI
Venue
2008
10.1016/j.cosrev.2008.10.003
Computer Science Review
Keywords
DocType
Volume
universal algebra,constraint satisfaction,polynomial time,graph homomorphism,constraint satisfaction problem
Journal
2
Issue
ISSN
Citations 
3
1574-0137
24
PageRank 
References 
Authors
0.91
103
2
Search Limit
100103
Name
Order
Citations
PageRank
Pavol Hell12638288.75
Jaroslav Nešetřil21432164.83