2.1.2. Feasibility view

Given a constraint where not all variables are fixed yet, a question is whether that constraint has at least one solution or not. We assume that all the not yet fixed variables must be assigned a value in a finite set of values. In this context we are looking for a necessary, and possibly sufficient, condition that can be evaluated in polynomial time with respect to the size of the arguments of that constraint.

For the $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraint we associate a variable-value graph where (1) each vertex corresponds to its variables and to the values that can be assigned to these variables, and (2) each edge corresponds to the fact that a variable can be assigned a given value. A necessary and sufficient condition is that the cardinality of the maximum matching, i.e. the maximum number of edges such that no two edges have a vertex in common, in this variable-value graph is equal to the number of variables.