A Dichotomy for 2-Constraint Forbidden CSP Patterns

A var(a) v} to v. If cpt(a, b) T then the two assignments (points) a, b are compatible and {a, b} is a compatibility In a In a CSP instance the aim is to determine the existence pattern, the compatibility of a pair of points a, b such that of an assignment of values to variables such that a set var(a) var(b) and (a, b) / E is undefined. A fundamental research question is the identification of tractable subproblems A binary CSP instance is a pattern 〈V, A, var, E, cpt〉 of CSP.