An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems

Abstract

We provide an optimal randomized linear-time algorithm for locally consistent constraints satisfaction problems with binary constraints and show that the algorithm can be derandomized.