Décompositions structurelles et sémantiques Rapport préliminaire

National audienceDans le cas des modèles graphiques, même les plus simples comme les CSP (réseaux de contraintes), les dé-compositions généralement proposées dans la littérature s'intéressent pour l'essentiel à la structure. Cela étant, afin de mieux appréhender un problème dans sa globalité, il serait souhaitable aussi de prendre en compte sa séman-tique, au sens des domaines des variables, et des relations de compatibilité qui leur sont associées via les contraintes. Dans cette note, il est proposé une nouvelle approche de la problématique qui prend justement en compte ces deux aspects pour définir une nouvelle forme de décom-position et son paramètre associé. L'une des ambitions d'une telle démarche et qui peut d'ailleurs constituer un réel défi pour la communauté, est de dépasser les limites actuellement posées par les décompositions arbo-rescentes de graphes de tree-width (ou largeur) bornée. On montre ainsi que le paramètre que nous proposons minore systématiquement la tree-width d'un réseau de contraintes binaires (cf. théorème 1) qui constitue "la" borne fondamentale actuelle pour le traitement de nom-breux problèmes combinatoires, dès lors qu'ils s'expriment en termes de graphes et qu'il s'agit de les résoudre par des approches fondées sur leur structure. Toutefois, si ce premier résultat semble démontrer la pertinence d'une telle approche, cette contribution doit être considérée comme une contribution très préliminaire à une éventuelle nouvelle voie de recherches