Minimal cycle cutset methods to solve constraint satisfaction problems

Abstract

Dechter [2] has proposed a cycle cutset method to solve Constraint Satisfaction Problems (CSPs). This method arbitrarily selects a set of nodes as cycle cutset and hence may contain some nodes which does not lie on any cycle. This will increase the size of the cutset and hence the time complexity of the method. In this paper, two minimal cycle cutset methods are presented. These methods first obtain a minimal cycle cutset in the constraint graph and then solve the CSP. Two algorithms to obtain a minimal cycle cutset in a graph are also presented here. The modified methods are tested on several randomly generated CSPs. On a class of constraint graph, the modified methods almost always show better performance.

Keywords:

• Algorithms
• Constraint satisfaction problems
• Minimal cycle cutset

C.R. Categories:

• G2.2
• I2.8