The power of arc consistency for CSPs defined by partially-ordered forbidden patterns

Martin Cooper (1, 2) , Stanislav Živný (3)

1 IRIT-ADRIA - Argumentation, Décision, Raisonnement, Incertitude et Apprentissage
2 UT3 - Université Toulouse III - Paul Sabatier
3 University of Oxford

Characterising tractable fragments of the constraint satisfaction problem (CSP) is an important challenge in theoretical computer science and arti ficial intelligence. Forbidding patterns (generic sub-instances) provides a means of defi ning CSP fragments which are neither exclusively language-based nor exclusively structure-based. It is known that the class of binary CSP instances in which the broken-triangle pattern (BTP) does not occur, a class which includes all tree-structured instances, are decided by arc consistency (AC), a ubiquitous reduction operation in constraint solvers. We provide a characterisation of simple partially-ordered forbidden patterns which have this AC-solvability property. It turns out that BTP is just one of fi ve such AC-solvable patterns. The four other patterns allow us to exhibit new tractable classes.

Mots clés: Arc consistency; Constraint satisfaction problem; Forbidden pattern; Tractability

Domaines: Intelligence artificielle [cs.AI]; Informatique et langage [cs.CL]; Apprentissage [cs.LG]; Logique en informatique [cs.LO]; Complexité [cs.CC]

Martin Cooper, Stanislav Živný. The power of arc consistency for CSPs defined by partially-ordered forbidden patterns. Logical Methods in Computer Science, 2017, 13 (4:26), pp.1-32. ⟨10.23638/LMCS-13(4:26)2017⟩. ⟨hal-02640799⟩