Dans cette thèse, nous étudions la complexité paramétrée de problèmes combinatoires dans les graphes. Plus précisément, nous présentons une multitude d’algorithmes de programmation dynamique ainsi que des réductions montrant que certains de ces algorithmes sont optimaux. Nous nous intéressons principalement à la treewidth, un paramètre de graphes pouvant être vu comme une mesure de distance entre la structure d’un graphe et la structure topologique d’un arbre. Certains de nos algorithmes sont aussi paramétrés par la taille de la solution demandée et le degré maximum du graphe donné en entrée. Nous avons obtenu un certain nombre de résultats dont certains d’entre eux sont listés ci-dessous. Nous présentons un encadrement du nombre de graphes étiquetés de treewidth bornée. Nous étendons le domaine d’application de la théorie de la bidimensionalité par contraction au delà des graphes ne contenant pas de graphe apex en tant que mineur. Nous montrons aussi que la technique des structures de Catalan, outil améliorant l’efficacité des algorithmes résolvant des problèmes de connexité lorsque le graphe d’entrée est creux, ne peut être appliquée à la totalité des problèmes de connectivité, même si l’on ne considère, parmi les graphes creux, que les graphes planaires. Nous considérons le problème F-M-Deletion qui, étant donné une collection de graphes F, un graphe G et un entier k, demande s’il est possible de retirer au plus k sommets de G de telle sorte que le graphe restant ne contienne aucun graphe de F en tant que mineur. Nous considérons aussi la version topologique de ce problème, à savoir F-TM-Deletion. Ces deux problèmes généralisent des problèmes de modification de graphes bien connus tels que Vertex Cover, Feedback Vertex Set et Vertex Planarization. En fonction de la collection de graphes F, nous utilisons différentes techniques de programmation dynamique pour résoudre F-M-Deletion et F-TM-Deletion paramétrés par la treewidth. Nous utilisons des techniques standards, la structure des graphes frontières et l’approche basée sur le rang. En dernier lieu, nous appliquons ces techniques algorithmiques à deux problèmes issus du réseau de communications, à savoir une variation du problème classique de domination et un problème consistant à trouver un arbre couvrant possédant certaines propriétés, et un problème issu de la bioinformatique consistant à construire un arbre contenant en tant que mineur (topologique) un ensemble d’arbres donnés correspondant à des relations d’évolution entre ensembles d’espèces. / In this thesis, we study the Parameterized Complexity of combinatorial problems on graphs. More precisely, we present a multitude of dynamic programming algorithms together with reductions showing optimality for some of them. We mostly deal with the graph parameter of treewidth, which can be seen as a measure of how close a graph is to the topological structure of a tree. We also parameterize some of our algorithms by two other parameters, namely the size of a requested solution and the maximum degree of the input graph. We obtain a number of results, some of which are listed in the following. We estimate the number of labeled graphs of bounded treewidth. We extend the horizon of applicability of the theory of contraction Bidimensionality further than apex-minor free graphs, leading to a wider applicability of the design of subexponential dynamic programming algorithms. We show that the Catalan structure technique, that is a tool used to improve algorithm efficiency for connectivity problems where the input graph is restricted to be sparse, cannot be applied to all planar connectivity problems. We consider the F-M-Deletion problem that, given a set of graphs F, a graph G, and an integer k, asks if we can remove at most k vertices from G such that the remaining graph does not contain any graph of F as a minor. We also consider the topological version of this problem, namely F-TM-Deletion. Both problems generalize some well-known vertex deletion problems, namely Vertex Cover, Feedback Vertex Set, and Vertex Planarization. Depending on the set F, we use distinct dynamic programming techniques to solve F-M-Deletion and F-TM-Deletion when parameterized by treewidth. Namely, we use standard techniques, the rank based approach, and the framework of boundaried graphs. Finally, we apply these techniques to two problems originating from Networks, namely a variation of the classical dominating set problem and a problem that consists in finding a spanning tree with specific properties, and to a problem from Bioinformatics, namely that of construcing a tree that contains as a minor (or topological minor) a set of given trees corresponding to the evolutionary relationships between sets of species.
| Identifer | oai:union.ndltd.org:theses.fr/2017MONTS065 |
| Date | 22 September 2017 |
| Creators | Baste, Julien |
| Contributors | Montpellier, Thilikos, Dimitrios M., Sau Valls, Ignasi |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0027 seconds