Abstract : Il est bien connu que les problèmes NP-difficiles peuvent être résolus optimalement par des algorithmes qui opèrent en temps exponentiel (ou pire). Des méthodes classiques, comme l’énumération exhaustive, les diverses versions de "branch-and-bound", la programmation dynamique, etc., sont très largement utilisées pour résoudre ces problèmes. Concernant la complexité au pire de cas de ces méthodes, à part éventuellement pour la programmation dynamique, nous avons seulement des évaluations assez triviales et directes. La conception des algorithmes faiblement exponentiels (programme de recherche systématiquement étudié seulement à partir des débuts des années 2000) tente de fournir des nouvelles méthodes de développement des algorithmes exacts ainsi que des outils mathématiques pour l’analyse de leur complexité au pire des cas. Cet exposé présentera les plus importants parmi ces méthodes et outils ainsi que des exemples de leur utilisation.

Abstract : Lorsque l’on considère un problème NP-difficile, différentes techniques permettent de concevoir des algorithmes de complexité certes exponentielle mais bien plus faible que celle obtenue par recherche exhaustive par exemple. Si le problème considéré est de plus NP-difficile à approcher, on peut alors se demander s’il est possible d’obtenir un algorithme approché certes non polynomial mais significativement plus rapide que les algorithmes exacts. Il s’agit autrement dit d’étudier la possibilité d’obtenir un compromis entre temps de calcul et qualité de la solution. Dans cet exposé, je présenterai quelques résultats et techniques relatifs à cette problématique des algorithmes approchés faiblement exponentiels, ainsi qu’à celle, voisine, des algorithmes approchés FPT.

Abstract : Dans cet exposé, je présenterai un algorithme de noyau polynomial pour le problème Proper Interval Completion, où l’instance consiste en un graphe G = (V,E) et un entier k et où l’objectif est de décider s’il existe un ensemble F inclus dans (VxV)E et de taille au plus k tel que le graphe H = (V, E?F) est un graphe d’intervalle propre. Pour conclure, je mettrai en parallèle ce résultat avec d’autres résultats connus pour des problèmes de complétion de graphes, et terminerai sur une conjecture pour caractériser les problèmes de complétion admettant un noyau polynomial.

Abstract : Un étiquetage L(2,1) d’un graphe est une fonction qui, à chaque sommet, associe un entier positif tel que : les étiquettes de sommets adjacents diffèrent d’au moins 2 ; pour tout couple de sommets ayant un voisin commun, leurs étiquettes sont différentes. La largeur d’un tel étiquetage L(2,1) est le plus grand entier utilisé pour étiqueter les sommets. Etant donné un graphe, le problème d’optimisation demande de calculer un étiquetage L(2,1) de plus petite largeur possible. Dans cet exposé nous présenterons un algorithme exponentiel pour résoudre ce problème NP-difficile en temps O(2.6488^n).

Abstract : De nombreux problèmes de graphes, difficiles (en complexité classique ou paramétrée) dans le cas général, peuvent être résolus efficacement lorsqu’ils sont restreints à des graphes de petite largeur arborescente. Du point de vue de la complexité paramétrée, très peu de problèmes de graphes sont connus pour ne pas admettre d’algorithme FPT lorsqu’ils sont paramétrés par la largeur arborescente du graphe donné en entrée, sous l’hypothèse que FPT?W[1]. Dans cet exposé, je présenterai une nouvelle collection de problèmes n’admettant pas d’algorithme FPT lorsque paramétrés par la largeur arborescente.