The Anatomy of Easy Problems: A Constraint-Satisfaction Formulation

Abstract

This work aims towards the automatic generation of advice to guide the solution of difficult constraintsatisfaction problems (CSPs). The advice is generated by consulting relaxed, easy models which are backtrackfree. We identify a subset of CSPs whose syntactic and semantic properties make them easy to solve. The syntactic properties involve the structure of the constraint graph, while the semantic properties guarantee some local consistencies among the constraints. In particular, problems supported by tree-like constraint graphs, and some width-2 graphs, can be easily solved and are therefore chosen as the target model for the relaxation scheme. Optimal algorithms for solving easy problems are presented and analyzed. Finally, an efficient method is introduced for extracting advice from easy problems and using it to speedup the solution of hard problems. I