On the Complexity of Achieving K-Consistency

A number of combinatorial search problems can be formulated as constraint satisfaction problems. Typically backtrack search is used to solve these problems. To counteract the frequent thrashing behaviour of backtrack search, methods have been proposed to precondition constraint satisfaction problems. These methods remove inconsistencies involving only a small number of variables from the problem. In this note we analyze the time complexity of the most general of these methods, Freuder's $k$-consistency algorithm. We show that it takes worst case time $O(n^{k})$, where $n$ is the number of variables in the problem.