Sur la complexité des algorithmes de backtracking et quelques nouvelles classes polynomiales pour CSP

National audienceThe question of tractable classes of constraint satisfaction problems (CSPs) has been studied for a long time, and is now a very active research domain. However, studies of tractable classes are typically very theoretical. They usually introduce classes of instances together with polynomial time algorithms for recognizing and solving them, and the algorithms can be used only for the new class. In this paper, we address the issue of tractable classes of CSPs from a di erent perspective. We investigate the complexity of classical, generic algorithms for solving CSPs (such as Forward Checking). We introduce a new parameter for measuring their complexity and derive new complexity bounds. By relating the com- plexity of CSP algorithms to graph-theoretic parameters, our analysis allows us to point at new tractable classes, which can be solved directly by the usual CSP algorithms in polynomial time, and without the need to recognize the classes in advance.L'étude des classes polynomiales, pour les problèmes de satisfaction de contraintes (CSP), constitue depuis longtemps un domaine de recherche important qui s'avère aujourd'hui très actif. Cependant, les travaux réalisés jusqu'à présent se sont révélés pour l'essentiel théoriques. En effet, ils se cantonnent en général à la définition de classes d'instances pour lesquelles des algorithmes polynomiaux ad hoc, à la fois pour la reconnaissance et pour la résolution, sont proposes. Ces algorithmes ne peuvent être, en fait, utilisés que pour le traitement d'une classe d'instances donnée. Ils s'avèrent ainsi difficilement exploitables en pratique, et ne sont donc pas exploités au sein de solveurs généraux. L'intérêt pratique des classes polynomiales est ainsi très limitée. Dans cet article, nous abordons la question des classes polynomiales CSP d'un point de vue différent de l'approche classique, en nous intéressant aux algorithmes que l'on peut retrouver dans les systèmes de résolution opérationnels. Pour cela, nous _étudions d'abord la complexité d'algorithmes génériques de résolution de CSP tels que le Forward-Checking par exemple. Cette étude s'appuie sur l'exploitation d'un paramètre issu de la théorie des graphes, et qui permet de proposer de nouvelles bornes de complexité. La mise en relation de ces nouvelles bornes avec certains résultats issus de la théorie des graphes nous permet d'exhiber de nouvelles classes polynomiales. De cette façon, nous montrons comment des algorithmes classiques de résolution de CSP peuvent traiter efficacement en pratique ainsi qu'en théorie, des instances de CSP, sans devoir reconnaître au préalable leur appartenance à d'éventuelles classes polynomiales