Multicoupes et sous-graphes induits : complexité et algorithmes
Institution:
Paris, CNAMDisciplines:
Directors:
Abstract EN:
In this thesis, we consider some problems of graph theory. First, we deal with cut and multicut probems and then, we study induced subgrpah problems. Nevertheless, these two parts share a common purpose : detremining a general overview of the cimplexity of theses problems by proving NP-completeness results or by d"esigning polynomial algrotithms 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 secon 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 vertives is fixed. Finally , we also some structural results for C3 free graphs.
Abstract FR:
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 pouis, dans un second temps, nous nous focalisons sur des problèmes de recherche de sous-graphes induits. Néammoins, 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 polynominaux, 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 typologies 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 ouvrant un ensemble T de sommets donnés. Après avouir prouvé la NP-complétude des cas généraux, nous nous focalisons davantage sur les cas ou la cardinalité de T est fixée. Nous donnons également plusieurs résultats structurels pour les graphes de maille suffisamment large.