Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 28 Avril 2015

Restrictions structurales pour le problème #CSP

par Johann Brault-Baron (lif, Marseille)

Le problème CSP (Constraint Satisfaction Problem) consiste à déterminer, étant donné un ensemble de contraintes, s’il existe une solution, c’est-à-dire un ensemble d'affectations des variables qui satisfait toutes les contraintes. C’est un problème NP-complet.

Nous nous intéressons ici au problème #CSP qui consiste à déterminer, étant donné un ensemble de contraintes, le nombre de telles solutions. C’est donc un problème NP-difficile.

À l'instar du problème CSP, on peut restreindre le type de contraintes possibles afin de s'assurer que le problème est polynomial. Cette approche a montré rapidement ses limites, et on s’est donc penché sur une autre alternative, qui consiste à placer des restrictions sur le graphe (ou l'hypergraphe) de contraintes, appelée « restrictions structurales ».

Cette approche a amené à définir de nombreuses nouvelles classes polynomiales, qui ont été toutes décrites et « synthétisées » dans une contribution récente et marquante de Sæther, Telle et Vatshelle. Les auteurs définissent un paramètre, qui, d'un certain point de vue, indique l'efficacité de tout algorithme de type « diviser pour régner ». Lorsque ce paramètre est borné, la classe correspondante a un problème #CSP de complexité polynomiale. Jusqu'à présent, toutes les restrictions structurales envisagées sont des cas particuliers d’une telle situation.

On décrit dans cet exposé une classe polynomiale pour #CSP qui échappe (étonnamment) à ce cadre, et qui a de plus l'avantage d'être reconnaissable en temps polynomial.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr