Detecting Unsatisfiable CSPs by Coloring the Micro-Structure

Abstract

Constraint satisfaction research has focussed on consistency checking using k-consistency and its variations such as arc-consistency, and path-consistency. We define a new form of consistency checking that is based on coloring the micro-structure graph of a constraint satisfaction problem (CSP). In our formulation, if the micro-structure graph of a CSP with n variables can be colored with n - 1 colors then the problem is unsatisfiable. This new notion of consistencyby -coloring is compared to arc-consistency. We provide examples that show that neither arc-consistency nor consistency-by-coloring is more powerful than the other in a theoretical sense. We also describe the results of preliminary computational experiments that compare consistency-by-coloring and arc-consistency. Introduction 1 Constraint satisfaction problems (CSPs) are often solved by backtracking algorithms that interleave search and consistency checking. Forward checking (Haralick & Elliot 1980) and maintained arc-con...