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 15 Novembre 2005

Les problèmes de motifs interdits restreints à des graphes connexes de degré borné sont des problèmes de satisfaction de contraintes

par Florent Madelaine (université de Durham)

Les problèmes de satisfaction de contraintes (CSP) forment une large classe de problèmes dans NP, qui contient des problèmes NP-complets tels SAT ou 3-Col. Fagin a montré que NP correspond exactement aux problèmes qui peuvent s'exprimer à l'aide de formules de la logique existentielle du second ordre (ESO). Feder et Vardi ont mis en évidence une restriction de ESO qui bien que trop expressive est "proche" de CSP: la logique MMSNP.

Dans des travaux précédents j'ai déterminé exactement la frontière entre CSP et MMSNP. En fait, plutôt que de travailler dans le contexte logique, j'ai donné une "traduction" combinatoire de MMSNP, à savoir la classe des problèmes de motifs (coloriés) interdits. Un exemple typique de problème de motif interdit qui n'est pas dans CSP est le problème de graphes "pas de triangle Monochromatique". Ce problème prend comme instance un graphe et accepte ce graphe si et seulement si il existe une partition de ces sommets en deux parties (deux "couleurs") telle que chaque partie soit sans triangle.

Plus récemment, je me suis penché sur le problème inverse: sous quelles restrictions (de la classe des instances), la logique MMSNP capture exactement CSP (avec les mêmes restrictions sur la classe des instances). Je donne un exemple d'une telle restriction. lorsque toute instance est connexe et de degré borné. Par exemple, le problème "pas de triangle Monochromatique" est en fait un CSP, si on restreint les instances à être à la fois connexes et de degré borné.

Dans une première partie de l'exposé, je vais résumer quelques résultats liés à CSP et MMSNP que je vais illustrer par plusieurs exemples. Dans une seconde partie de l'exposé, je vais essayer de donner l'intuition de la preuve du résultat suivant. les problèmes de motifs interdits sont en fait des problèmes de satisfaction de contraintes lorsque les instances sont à la fois connexes et de degré borné. Finalement, je vais conclure par quelques questions.

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