Dans cette thèse, nous étudions des problèmes de modification de graphes, dont le but est d'appliquer un minimum de modifications d'un certain type au graphe donné en entrée, de sorte que le graphe résultant appartienne à une certaine classe de graphes H cible. Beaucoup de problèmes connus peuvent être exprimés comme des problèmes de modification de graphes, d'où l'intérêt considérable porté au sujet.

Plus précisément, nous étudions des problèmes de modification de graphes sous le point de vue de la complexité paramétrée, qui consiste à exprimer le temps d'exécution d'un algorithme non seulement en fonction de la taille n de l'entrée, mais aussi en fonction d'autres paramètres. Le paramètre considéré ici est généralement la taille k du modulateur (i.e., les sommets du graphe donné en entrée qui sont modifiés), ou une autre mesure sur le modulateur. Nous cherchons principalement des algorithmes dit FPT, c'est-à-dire qui terminent en temps f(k) · nc pour une fonction f et une constante c.