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 5 Décembre 2000

Réductions hamiltoniennes exactes

par Régis Barbanchon (GREYC)

De nombreux problèmes NP-complets ne sont pas seulement vérifiables en temps polynômial mais aussi en temps linéaire. Parmi ceux-ci, certains sont linéairement réductibles entre eux, alors que l'on conjecture que c'est impossible pour d'autres. Hamilton et Sat sont interessants sous cet aspect.

Une réduction exacte est une réduction à la fois linéaire et parcimonieuse (ie. elle preserve le nombre de solutions). Il est connu que les variantes de Hamilton non-planaires sont équivalentes sous interréduction exacte lorsque le degré des graphes n'est pas borné. Il est également connu que Sat non-planaire est exactement réductible à Hamilton non-planaire. A notre connaissance, il n'existe pas les mêmes résultats pour les graphes planaires et/ou à degré borné.

Dans cet exposé, nous établirons principalement trois choses: * Toutes les variantes citées de Hamilton non-planaires sont exactement interréductibles, même lorsque le degré est borné à 3; * Toutes les variantes citées de Hamilton planaires sont exactement interréductibles, même lorsque le degré est borné à 3; * Sat planaire est exactement réductible à Hamilton planaire. Ces résultats seront obtenus par une méthode uniforme de réduction utilisant un arsenal homogène de gadgets modulaires inspirés des circuits électroniques. Nous pensons que s'il est très difficile de montrer que Hamilton n'est pas linéairement réductible à Sat, il sera peut-être plus facile de d'obtenir un résultat de non expressibilité si la réduction impliquée est plus stricte. A cet effet, la transformation exacte représente une piste.

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