Characterising tractable fragments of the constraint satisfaction problem(CSP) is an important challenge in theoretical computer science and artificialintelligence. Forbidding patterns (generic sub-instances) provides a means ofdefining CSP fragments which are neither exclusively language-based norexclusively structure-based. It is known that the class of binary CSP instancesin which the broken-triangle pattern (BTP) does not occur, a class whichincludes all tree-structured instances, are decided by arc consistency (AC), aubiquitous reduction operation in constraint solvers. We provide acharacterisation of simple partially-ordered forbidden patterns which have thisAC-solvability property. It turns out that BTP is just one of five suchAC-solvable patterns. The four other patterns allow us to exhibit new tractableclasses.
展开▼
