Résumé
Dans cette thèse, nous fournissons un cadre méta-algorithmique capitalisant sur les conséquences algorithmiques de la série séminale des articles de Robertson et Seymour traitant les mineurs des graphes. Notre perspective méta-algorithmique consiste en la preuve de méta-théorèmes algorithmiques, qui fournissent des conditions mathématiques générales permettant la dérivation automatique d’algorithmes efficaces. De tels théorèmes comportent généralement deux types de conditions, une logique et une combinatoire, de sorte que tout problème exprimable dans le cadre de la condition logique peut être résolu efficacement, sous une définition appropriée de ce terme, lorsque ses entrées sont limitées par la condition combinatoire.Les méta-théorèmes algorithmiques démontrés dans cette thèse peuvent être résumés en deux résultats principaux. Tout d’abord, nous considérons la logique des chemins disjoints, qui est une extension de la logique du premier ordre avec des prédicats atomiques supplémentaires qui expriment l’existence de chemins disjoints entre sommets. Nous montrons que les problèmes définissables dans la logique des chemins disjoints peuvent être résolus en temps cubique sur des graphes qui excluent certains graphes fixes comme mineurs topologiques. Nous définissons également un cadre de logiques composées, qui modélisent le schéma modulateur/cible de divers aspects des problèmes de modification de graphes. Notre deuxième méta-théorème algorithmique concerne des problèmes définissables dans la logique composée obtenue en combinant, du coté de la cible, la puissance expressive de la logique des chemins disjoints, et du coté du modulateur, la logique monadique du second ordre. Pour de tels problèmes, nous montrons qu’ils peuvent être résolus en temps quadratique sur des graphes qui excluent certains graphes fixes comme mineurs. Les résultats obtenus et leurs preuves peuvent être interprétés comme une méta-algorithmisation de l’applicabilité du théorème du mur plat et de la technique du sommet non pertinent pour de grandes familles de problèmes de routage et de modification de graphes.Pour prouver nos méta-théorèmes algorithmiques, nous développons un cadre combinatoire et algorithmique composé de nouvelles variantes et améliorations du théorème du mur plat et du théorème de liaison unique, permettant leur application et leur adaptation dans un contexte méta-algorithmique. Nous dérivons aussi une borne supérieure sur le nombre de sommets des obstructions mineures des k-apices des classes de graphes closes par mineurs.Nous considérons également deux méta-problèmes qui sont englobés dans notre cadre méta- algorithmique : les problèmes de F-Mineur-Suppression et de F-Mineur Topologique-Suppression, où, étant donné un ensemble de graphes F, un graphe G et un entier k, nous demandons si nous pouvons supprimer au plus k sommets de G de telle sorte que le graphe restant ne contienne aucun graphe de F en tant que mineur ou en tant que mineur topologique, respectivement. Pour ces deux problèmes, nous obtenons des algorithmes améliorés les résolvant respectivement sur des graphes généraux et sur des graphes plongables sur une surface de genre fixe.