2011/03/31 by David A. Cohen, Martin Cooper, Martin C. Cooper +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Artificial intelligence #Binary relation #Class (philosophy) #Computer science #Constraint (computer-aided design) #Constraint Satisfaction and Optimization #Constraint satisfaction problem #Discrete mathematics #Hypergraph #Mathematics #Theoretical computer science #Tuple #cs.AI #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.1613/jair.3651
published as Journal Of Artificial Intelligence Research, Volume 45, pages 47-78, 2012
openalex publication_date 2012/09/20 · arxiv created 2014/07/08 · arxiv updated 2014/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The constraint satisfaction problem (CSP) is a general problem central to computer science and artificial intelligence. Although the CSP is NP-hard in general, considerable effort has been spent on identifying tractable subclasses. The main two approaches consider structural properties (restrictions on the hypergraph of constraint scopes) and relational properties (restrictions on the language of constraint relations). Recently, some authors have considered hybrid properties that restrict the constraint hypergraph and the relations simultaneously. Our key contribution is the novel concept of a CSP pattern and classes of problems defined by forbidden patterns (which can be viewed as forbidding generic sub-problems). We describe the theoretical framework which can be used to reason about classes of problems defined by forbidden patterns. We show that this framework generalises certain known hybrid tractable classes. Although we are not close to obtaining a complete characterisation concerning the tractability of general forbidden patterns, we prove a dichotomy in a special case: classes of problems that arise when we can only forbid binary negative patterns (generic sub-problems in which only disallowed tuples are specified). In this case we show that all (finite sets of) forbidden patterns define either polynomial-time solvable or NP-complete classes of instances.