Detecting Unsatisfiable CSPs by Coloring the Micro-Structure

Daya Ram Gaur, W. Ken Jackson, William S. Havens

Constraint satisfaction research has focused 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 consistency-by-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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.