On the power of structural decompositions of graph-based representations of constraint problems Original Research Article

The Constraint Satisfaction Problem (CSP) is a central issue of research in Artificial Intelligence. Due to its intractability, many efforts have been made in order to identify tractable classes of CSP instances, and in fact deep and useful results have already been achieved. In particular, this paper focuses on structural decomposition methods, which are essentially meant to look for near-acyclicity properties of the graphs or hypergraphs that encode the structure of the constraints interactions. In general, constraint scopes comprise an arbitrary number of variables, and thus this structure may be naturally encoded via hypergraphs. However, in many practical applications, decomposition methods are applied over suitable graph representations of the (possibly non-binary) CSP instances at hand. Despite the great interest in such binary approaches, a formal analysis of their power, in terms of their ability of identifying islands of tractability, was missing in the literature.