Light Integration of Path Consistency for Solving CSPs

Many local consistency properties have been exploited in solving constraint satisfaction problems. The objective is to reduce the search space and consequently improve search methods. It has been shown that maintaining arc- consistency during search is very useful in solving CSPs. The use of stronger local consistency forms (like path consistency) is still limited since they need complicated data structures to be managed and the constraint graph may be modified. In this paper, we propose a possible way to get benefits from using, in a preprocessing step, a partial form of path consistency and arc consistency based on support intervals notion.