[Freuder, 1991]. At the end of the process, the leaves of the discrimination tree are annotated with the equivalence NI values for the variable. The complexity of this process is O(n 2d 2), where n is the number of variables and d is the maximum domain size. Alternatively, one can build a refutation tree, which proceeds by splitting the domain of the variable [Likitvivatanavong and Yap, 2008]. The lower bound of the worst-case complexity of the refutation tree is smaller than that of the discrimination tree. However, it is not clear whether the difference is meaningful in practice. Further, the discrimination tree can be directly used to implement forward checking at no additional cost [Beckwith *et al.*, 2001], but it is not clear yet whether or not the same can be done with the refutation tree.

For non-binary constraints, neighborhood interchangeable values can be detected by constructing non-binary discrimination trees for each variable [Lal et al., 2005]. As described in [Lal *et al.*, 2005], the process also allows the use of forward checking during search. The complexity to build a non-binary discrimination tree for a single variable is O(n deg a k+1(1−t)), where n is the number of variables, deg is the maximum degree of a variable, a is the maximum domain size, and t is the tightness of the constraints, defined as the ratio of the number of forbidden tuples over the number of all possible tuples.

K-interchangeability (KI) [Freuder, 1991] For k ≥ 2, two values, a and b for a CSP variable X, are *k-interchangeable* iff a and b are fully interchangeable in any subproblem of the CSP induced by X and (k − 1) other variables. Values a and b are 3-I in Figures 2 and 3 but not in Figure 1.

K-interchangeable values can be identified by a modification of the discriminationtree algorithm for NI. The complexity of the process is O(n kd k) [Freuder, 1991].

Theorem 1. NI → KI → FI, see [Freuder, 1991].

For 2 *< i < j <* |V |, i-interchangeability is a sufficient but not necessary condition for j-interchangeability. NI is 2-interchangeability and FI is |V |-interchangeability.

Hence, NI → KI → FI. a and b in Figure 1 are FI but not 3-I, and in Figure 3 they are 3-I but not NI.

## 2.2 Extended Interchangeability: Weak Forms

Below, we discuss three weak forms of interchangeability introduced in [Freuder, 1991] (i.e., subproblem interchangeability, partial interchangeability, and substitutability) and a number of other related concepts.

Subproblem interchangeability (SPrI) [Freuder, 1991] Two values are *subproblem interchangeable*, with respect to a subset of variables S, iff they are fully interchangeable with regards to the solutions of the subproblem of the CSP induced by S.

Partial interchangeability (PI) [Freuder, 1991] Two values are *partially interchangeable* with respect to a subset S of variables, iff any solution involving one implies a solution involving the other with possibly different values for variables in S. In Figure 4, a and b are PI wrt S, shown with the dotted line.