Multicoupes et sous-graphes induits : complexité et algorithmes.

In this thesis, we consider some problems of graph theory. First, we deal with cut and multicut problems and then, we study induced subgraph problems. Nevertheless, these two parts share a common purpose : determining a general overview of the complexity of these problems by proving NP-completeness results or by designing polynomial algorithms with low running times. In the first part, we tackle cut and multicut problems. We study the consequences of the addition of a cardinality constraint and show the NP-completeness of the general cases. Besides, we give complexity results for some particular graphs such as directed stars and undirected paths, and for the polynomial cases, we design several algorithms using dynamic programming or lagrangian relaxations. Next, we generalize these problems by considering multicriteria versions of the (multi)cut problems. We obtain some NP-completeness results in some very specific classes of graphs like undirected paths and cycles. In the second part, we focus on the detection of specific induced subgraphs. More precisely, we look for induced paths, induced cycles or induced trees covering a given set of vertices. After proving the NP-completeness of the general cases, we consider the cases where the number of prescribed vertices is fixed. Finally, we also give some structural results for C3-free graphs.Dans ce travail de thèse, nous nous intéressons à plusieurs problèmes de théorie des graphes. Dans un premier temps, nous étudions différents problèmes de coupes et de multicoupes puis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néanmoins, ces deux parties suivent la même ligne directrice : donner une vue d'ensemble de la complexité des problèmes en établissant leur NP-complétude ou en déterminant un algorithme polynomial de moindre complexité. Dans la première partie de la thèse, nous abordons les problèmes de coupes et de multicoupes. Tout d'abord, nous étudions la conséquence de l'ajout d'une contrainte de cardinalité à ces deux types de problèmes et démontrons leur NP- complétude dans le cas général. Puis, nous déterminons leur complexité dans plusieurs classes de graphes particuliers telles que les étoiles orientées et les chaînes en élaborant, pour les cas polynomiaux, différents algorithmes reposant principalement sur la programmation dynamique et l'utilisation de relaxations lagrangiennes. Nous généralisons ensuite cette approche en considérant les versions multicritères des problèmes de coupes et de multicoupes. Nous prouvons que ces derniers sont NP-complets même dans des topologies très simples comme les chaînes ou les cycles. Dans la seconde partie de ce mémoire, nous abordons des problèmes de recherche de sous-graphes induits. Nous nous intéressons principalement à la recherche d'arbres, de chaînes et de cycles induits couvrant un ensemble T de sommets donnés. Après avoir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas où la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large