Kernels and quasi-kernels in digraphs.

Noyaux et quasi-noyaux dans les graphes orientés Une notion importante de la théorie des graphes orientés est celle de noyau. Cette notion fut introduite par Morgenstern et von Neumann pour l'étude des stratégies gagnantes dans les jeux combinatoires et possède désormais de nombreuses applications, dans d'autres domaines de la théorie des graphes mais aussi en théorie des jeux, en économie ou en logique. Dans un graphe orienté D=(V,A), un noyau est un sous-ensemble N de sommets qui est à la fois indépendant -- aucune paire de sommets dans N n'est reliée par un arc -- et absorbant-- tout sommet hors de N est origine d'un arc vers un élément de N. Tous les graphes ne possèdent pas de noyau comme le montre l'exemple des circuits de longueur impaire. Décider si un graphe possède un noyau est d'ailleurs NP-complet. Il existe cependant des graphes pour lesquels ce problème de décision est trivial : un graphe parfait orienté sans circuit orienté de longueur 3 possède toujours un noyau. C'est la conséquence d'un théorème de Boros et Gurvich, prouvé par ces derniers en 1996 (et conjecturé par Berge et Duchet en 1980). Cependant, la complexité algorithmique de trouver un noyau n'est pas connue pour cette classe, et constitue une question ouverte importante. La première partie de cette thèse consiste en l'étude de cette question. Le caractère polynomial de quelques cas particuliers avait déjà été établi, comme les graphes triangulés ou étaient connu depuis longtemps, comme les graphes bipartis, et nous étendons cette liste avec notamment une généralisation des graphes de comparabilités.Chv'atal et Lov'asz ont montré en 1974 qu'une petite modification de la définition de noyau assurait son existence systématique : ils ont prouvé que tout graphe orienté possède un sous-ensemble N indépendant tel que tout sommet hors de N possède un chemin de longueur au plus 2 vers un élément de N. Un tel sous-ensemble est un quasi-noyau. Leur preuve fournit d'ailleurs un algorithme polynomial pour en trouver un dans tout graphe orienté. Mais une étude algorithmique approfondie des quasi-noyaux n'avait encore jamais été menée, et constitue. Cette étude a permis de répondre à des questions naturelles comme celle de l'existence de deux quasi-noyaux distincts ou celle de la taille minimale d'un quasi-noyau, toutes deux motivées par une conjecture d'Erdős et Székely de 1976.La deuxième partie de cette thèse est constituée de l'étude algorithmique des quasi-noyaux ainsi que l'étude de cas partiuliers relatifs à la conjecture Erdős et Székely.