Decomposition of Domains Based on the Micro-Structure of Finite Constraint-Satisfaction Problems

Philippe Jégou

In this paper, we present a method for improving search efficiency in the area of Constraint-Satisfaction-Problems in finite domains. This method is based on the analysis of the "micro-structure" of a CSP. We call micro-structure of a CSP, the graph defined by the compatible relations between variable-value pairs: vertices are these pairs, and edges are defined by pairs of compatible vertices. Given the micro-structure of a CSP, we can realize a preprocessing to simplify the problem with a decomposition of the domains of variables. So, we propose a new approach to problem decomposition in the field of CSPs, well adjusted in cases such as classical decomposition methods are without interest (i.e. when the constraint graph is complete). The method is described in the paper and a complexity analysis is presented, given theoretical justifications of the approach. Furthermore, two polynomial classes of CSPs are induced by this approach, the recognition of them being linear in the size of the instance of CSP considered.

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.