Reformulating the Dual Graphs of CSPs to Improve the Performance of Relational Neighborhood Inverse Consistency

Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a new local consistency property for binary Constraint Satisfaction Problems (CSPs). Two advan-tages of the algorithm for enforcing NIC is that it automat-ically adapts its filtering power to the local connectivity of the network and has insignificant space overhead. However, studies on binary CSPs have shown that enforcing NIC is not effective on sparse graphs and too costly on dense graphs. In (Woodward et al. 2011), we introduced an algorithm for enforcing Relational Neighborhood Inverse Consistency (RNIC), which is an extension of NIC to non-binary CSPs. In this paper, we discuss how we enhance the propagation effectiveness of our algorithm and reduce its computationa