Reformulating R(∗,m)C with Tree Decomposition

Local consistency properties and algorithms for enforc-ing them are central to the success of Constraint Pro-cessing. Recently, we have demonstrated the impor-tance of higher levels of consistency and the effective-ness of their algorithms for solving difficult problems (Karakashian et al. 2010; Woodward et al. 2011). In this paper, we introduce two reformulation techniques for improving the effectiveness of our algorithm for the relational consistency property R(∗,m)C (Karakashian et al. 2010). Both techniques exploit a tree decomposi-tion of the constraint network of a Constraint Satisfac-tion Problem (CSP), which is a tree embedding of the network. Our first reformulation technique exploits the structure of the decomposition tree and the state of th