AAAI Publications, Twenty-Sixth AAAI Conference on Artificial Intelligence

Font Size: 
A Dichotomy for 2-Constraint Forbidden CSP Patterns
Martin C. Cooper, Guillaume Escamocher

Last modified: 2012-07-14


Novel tractable classes of the binary CSP (constraint satisfaction problem) have recently been discovered by studying classes of instances defined by excluding subproblems described by patterns. The complete characterisation of all tractable classes defined by forbidden patterns is a challenging problem. We demonstrate a dichotomy in the case of forbidden patterns consisting of two constraints.


forbidden, pattern, tractability

Full Text: PDF