A Dichotomy for 2-Constraint Forbidden CSP Patterns

Authors

  • Martin Cooper Institut de Recherche en Informatique de Toulouse
  • Guillaume Escamocher Institut de Recherche en Informatique de Toulouse

DOI:

https://doi.org/10.1609/aaai.v26i1.8131

Keywords:

forbidden, pattern, tractability

Abstract

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.

Downloads

Published

2021-09-20

How to Cite

Cooper, M., & Escamocher, G. (2021). A Dichotomy for 2-Constraint Forbidden CSP Patterns. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 464-470. https://doi.org/10.1609/aaai.v26i1.8131

Issue

Vol. 26 No. 1 (2012): Twenty-Sixth AAAI Conference on Artificial Intelligence

Section

Constraints, Satisfiability, and Search