Le premier volet de cette thèse porte sur l'étude de graphes dont les sommets sont colorés. Nous étudions comment la recherche d'ensembles particuliers de sommets est affectée lorsqu'on ajoute la contrainte qu'ils soient tropicaux, c'est à dire contiennent au moins un sommet de chacune des couleurs.Cette contrainte additionnelle tend à fortement augmenter la complexité des problèmes. Par exemple, la recherche d'un plus petit ensemble dominant tropical, et celle d'une plus petite couverture par sommet tropicale, sont APX-complets même restreints aux chemins. La recherche du plus petit sous-graphe connexe tropical d'un graphe est elle NP-complète, même restreinte aux arbres. Cependant, ajouter un contrainte sur le nombre de couleurs permet souvent de réduire la complexité. Par exemple, sans restrictions sur le type de graphes en entrée, la recherche d'un sous-graphe connexe tropical s'effectue en temps polynomial pourvu que le nombre de couleurs reste logarithmique en la taille du graphe. De plus, nous montrons divers résultats structurels qui lient la taille d'un sous-graphe connexe tropical minimum à des paramètres du graphe tels que le nombre de couleurs, le nombre d'arêtes, le degré minimum, ... Dans le second volet, nous étudions des jeux sur des graphes, appelés jeux de défense, où des attaquants ciblent des sommets et des défenseurs protègent des sous-graphes. On s'intéresse à l'existence d'un équilibre de Nash lorsque les défenseurs protègent des chemins de taille au plus p. Lorsque chaque défenseur protège exactement une arête, nous montron<s notamment que déterminer si le jeu pour un graphe G, n défenseurs et k attaquants, admet un équilibre de Nash revient à déterminer si G possède un indépendant dominant de taille inférieure ou égale à k, problème NP-complet dans le cas général.Plus généralement, lorsque les défenseurs protègent des chemins de taille p, l'existence d'un équilibre de Nash dans un jeu avec n défenseurs est liée à la notion de p-indépendant. Un ensemble de sommets est p-indépendant si toutes les paires de sommets sont à distance supérieure à p. Déterminer l'existence d'un p-indépendant maximal de taille inférieure ou égale à k dans un graphe quelconque est NP-complet. Notre algorithme Min2stablemax permet de calculer la taille minimum d'un 2-indépendant maximal dans un arbre. / The first pane of this thesis is on the study of vertex-colored graphs. We look at the tractability of asserting the existence of particular sets of vertices on a graph with the added constraint that the sets must be tropical, i.e. they must contain at least one vertex of each of the colors in the graph.This additional constraint tends to make the problems way less tractable. For instance, finding a minimum tropical dominating set, or a minimum tropical vertex cover, are APX-complete problems even when restricted to paths. Finding the smallest tropical connected subgraph is also NP-complete even when restricted to trees. However, restricting the number of colors will usually make problems more tractable. For instance, finding a connected tropical subgraph (on any graph) can be done in polynomial time as long as the number of colors is logarithmic in the size of the graph. Moreover, we show some structural results that links the size of a minimum connected subgraph to parameters such as the number of colors, the number of edges, the minimum degree…The second pane is on the study of some games on graphs, called defense games, in which multiple attackers target vertices and multiple defenders protect subgraphs.We focus on the existence of a Nash equilibrium when defenders protect paths of size at most p.When each defender protects exactly one edge, we show among other results that the game on a graph G with n defenders and k attackers admits a Nash equilibrium if and only if there exists a dominating set of size at most k in G, which is NP-complete in the general case.Similarly, when each defender protects a path of size at most p, the existence of a Nash equilibrium is linked to the notion of p-independent, i.e. a set of vertices such that every pair of elements of the set is at distance greater than p.Determining the existence of a maximal p-independent of size at most k is NP-complete, but our Min2stablemax algorithm can compute the minimum size of a maximal 2-independent set in a tree.
| Identifer | oai:union.ndltd.org:theses.fr/2015PA112235 |
| Date | 24 September 2015 |
| Creators | Anglès d'Auriac, Jean-Alexandre |
| Contributors | Paris 11, Manoussakis, Yannis |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | French |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text, Image, StillImage |
Page generated in 0.0018 seconds