Séance Séminaire

Séminaire des Doctorant·e·s

Dénoyautage de graphes

Le dénoyautage est une technique standard en horticulture (en particulier en ce qui concerne les cerisiers et les oliviers ; au printemps, lorsqu'il fait bon lézarder à l'ombre) qui consiste à extraire le noyau du fruit : en effet pourquoi conserver la chair du fruit alors que le noyau à lui seul contient toute l'information génétique nécessaire pour reconstituer un arbre entier (lequel produira de nouveaux fruits, eux même dénoyautables). Pour les graphes c'est la même chose, on peut supprimer toutes les parties qui n'apportent pas d'information pour la résolution d'un problème. Je commencerai mon exposé par quelques rappels élémentaires sur les graphes, les algorithmes, la complexité. Je ferai ensuite une introduction à la complexité paramétrée et aux noyaux. Ces deux domaines sont des formalisations de méthodes déjà existantes comme la réduction de données ou le pré-calcul. D'une part, la complexité paramétrée cherche à faire une analyse plus précise de la complexité d'un problème: le temps calcul est compté en fonction de la taille des données et d'un paramètre à choisir ; c'est une façon de contourner le problème posé par la NP-complétude. D'autre part, l'extraction de noyaux est une méthode qui consiste a réduire les données (les transformer en données équivalentes) tout en garantissant la taille des données réduites ; cette méthode fournit en particulier de bons algorithmes paramétrés, mais peut avoir d'autres applications. En fonction du temps qu'il me restera je ferai un exemple simple d'extraction de noyau, basé sur une méthode standard proposée par Alber, Fellows et Niedermeier. Bien sûr je ferai en sorte que l'exposé soit accessible aux personnes non-initiées aux sciences ésotériques et j?espère qu'il pourra se faire de façon interactive.