The main idea of constraint propagation is notifying all of the constraints in the system about the removal of values of some variables, so that they can update themselves accordingly. It is well known that constraint propagation is the basic operation in all constraint programming tools. Thus, an improvement in the constraint propagation procedure will immediately affect the performance of the constraint-solving system.

The authors of this paper propose a simple, efficient algorithm that can accelerate constraint propagation. The proposed algorithm, which is based mainly on the well-known arc consistency 3 (AC3), can easily be incorporated into a constraint solver engine in order to efficiently solve hard constraint satisfaction problems. This improved algorithm is the authors’ main contribution.

The authors compare their new algorithm with AC3 and AC6 on random and realistic constraint satisfaction problem instances. The obtained results show that the proposed algorithm is better than AC3 in terms of constraints checking and central processing unit (CPU) time, and that it is comparable to AC6, the fastest fine-grained algorithm. In addition, the authors prove that the proposed algorithm has an optimal worst-case time complexity of O(ed2), and a space complexity of O(ed), where e is the number of constraints and d is the size of the maximum domain in a problem. These new results show effectively that the authors’ algorithm is better than AC3 for larger complexities.

The authors also discuss the application of the proposed algorithm to path consistency and nonbinary constraints. I expected to see an application of the algorithm to concrete nonbinary constraint problems; this was not presented in the paper. Finally, the paper is well written and well organized, with precise objectives. It can be easily understood, even by nonspecialists.