Sous-graphes connexes tropicaux minimum

Télécharger le fichier pdf d’un mémoire de fin d’études

Graphes sommet-colorés

— Une coloration d’un graphe G = (V; E) est une fonction c qui à chaque sommet de V associe une couleur. On notera Gc le graphe G muni d’une coloration utilisant c couleurs. De plus, on désignera la couleur du sommet u par c(u) et les couleurs des sommets d’un sous-graphe H par c(H). Une coloration c d’un graphe G est dite propre si pour toute paire u et v de sommets de G adjacents, on a c(u) 6= c(v). On dénotera (G) le nombre chromatique d’un graphe G, c’est-à-dire, le nombre de couleurs minimum sur toutes les colorations propres de G. De plus, on notera C(G) l’ensemble des couleurs utilisés par la coloration de Gc, c’est-à-dire C(G) = c(G).
— Un ensemble de sommets S du graphe Gc est dit tropical si pour tout sommet u de Gc, il existe un sommet v dans S tel que c(u) = c(v). Autrement dit, S contient au moins un représentant pour chacune des couleurs présentes dans le graphe.
— Un ensemble de sommets S de Gc est arc-en-ciel s’il est tropical et que pour toute paire de sommets u et v de S, c(u) 6= c(v), c’est-à-dire que S contient exactement un représentant pour chacune des couleurs présentes dans le graphe.

Théorie des jeux

La théorie des jeux est un domaine des mathématiques visant à modéliser des situations où diverses entités interagissent de façon compétitive ou col-laborative, chacune cherchant à maximiser ses propres gains, ou à minimiser ses propres pertes. Formellement, un jeu est défini par
— Un ensemble de joueurs.
— Pour chaque joueur, un ensemble de stratégies possibles, où chaque stratégie représente l’ensemble des choix que le joueur fera durant une partie. Un profil est l’attribution à chaque joueur d’une de ses stratégies, décrivant ainsi l’ensemble des choix de tous les joueurs lors d’une partie.
— Pour chaque joueur, une fonction de profit, qui a un profil associe un nombre, qu’on appelle le profit du joueur.
Un équilibre de Nash[Nas50, Nas51] est un profil s tel qu’aucun des joueurs ne puisse unilatéralement améliorer son profit personnel. Formellement, s est un équilibre de Nash si pour tout joueur i, et pour tout profil s0 ne différant de s que sur la stratégie choisi par i, le profit de i est plus important dans s que dans s0.

Complexité

On va donner une présentation informelle des concepts de complexité algorithmique qui seront utilisés dans ce document.
La classe de problèmes NP contient l’ensemble des problèmes de déci-sion pour lesquels il existe un algorithme pour vérifier une solution en un nombre polynomial d’étapes élémentaires. Cependant, cela ne garantit pas qu’il existe un algorithme capable de trouver une solution en un nombre poly-nomial d’étapes. Un problème NP-complet est un problème tel que démontrer qu’il peut être résolu en un nombre polynomial d’étapes implique que tous les problèmes de NP puissent eux aussi être résolus en un nombre polynomial d’étapes. Démontrer qu’un problème donné est NP-complet se fait généra-lement en montrant que si l’on peut le résoudre en un nombre polynomial d’étapes, alors on pourra résoudre en un nombre polynomial d’étapes un autre problème, dont on a déjà démontré qu’il est NP-complet. On notera parfois par abus de langage qu’un problème d’optimisation est NP-complet, ce qui revient à dire que le problème de décision associé est NP-complet.
Étant donné un problème d’optimisation, un algorithme fournit une ap-proximation dans un facteur > 1 (aussi notée -approximation) si, pour toute instance du problème donnée en entrée, en notant OPT la taille d’une solution optimale et SOL la taille de la solution renvoyée par l’algorithme, on a 1 OPT SOL OPT. Pour un problème de maximisation, cela revient donc à 1 OPT SOL, et pour un problème de minimisation, à SOL OPT. On dénote par APX la classe des problèmes pour lesquels il existe une machine de Turing déterministe et un certain tel que la machine de Turing calcule une -approximation du problème en temps polynomial. Un schéma d’approximation en temps polynomial (polynomial time approxima-tion scheme, PTAS) pour un problème donné est une fonction qui pour tout
> 1 fournit un algorithme polynomial renvoyant une -approximation du problème. Une PTAS-réduction est une réduction en temps polynomial d’un problème vers un autre problème qui conserve les approximations. Formel-lement, une réduction d’un problème A vers un problème B est une PTAS-réduction si elle associe en temps polynomial à toute instance de A une instance de B et qu’il existe une fonction f :]1; 1[!]1; 1[ telle qu’à partir d’une f( )-approximation de l’instance de B, on sache construire en temps polynomial une -approximation de l’instance de A. De ce fait, s’il existe une PTAS-réduction d’un problème A vers un problème B et qu’il existe une PTAS pour le problème B, alors il existe une PTAS pour le problème A. Un problème est APX-difficile si tout problème dans APX se PTAS-réduit vers lui. Un problème est APX-complet s’il est à la fois APX-difficile et dans APX. De plus, si P 6= N P , alors il existe des problèmes dans APX qui ne sont pas APX-complets[CKST95].
Ensemble dominant :
Entrée : Un graphe G et un entier k.
Question : Existe-t-il un ensemble dominant de taille k dans G ?
Ensemble dominant est APX-difficile d’après le théorème 3.3. de [AK00a] qui garantit que Ensemble dominant restreint aux graphes de dégré maxi-mum 3 est APX-complet.
Ensemble dominant indépendant :
Entrée : Un graphe G et un entier k.
Question : Existe-t-il un ensemble indépendant maximal de taille k dans G ?
On rappelle qu’un ensemble indépendant maximal de G est aussi un domi-nant de G. Ensemble dominant indépendant est NP-complet d’après [GJ79].
3-SAT :
Entrée : Une formule sous forme clausale avec 3 littéraux par clause.
Question : Existe-t-il une assignation des variables telle que la formule soit vérifiée ?
3-SAT est NP-complet d’après [Coo71].
SAT-3-OCC :
Entrée : Une formule sous forme clausale où chaque variable apparait dans au plus 3 clauses.
Question : Existe-t-il une assignation des variables telle que la formule soit vérifiée ?
SAT-3-OCC est NP-complet d’après [GJ79].
Couverture par sommets :
Entrée : Un graphe G = (V; E) et un entier k.
Question : Existe-t-il un ensemble S de k sommets de V tel que toute arête de E ait l’une de ses extrémités dans S ?
Couverture par sommets est APX-complet, même lorsque les graphes possibles en entrée sont restreints aux graphes cubiques[AK00b].
Couverture par ensembles :
Entrée : Un ensemble fini d’éléments U appelé univers, une collection C de sous-ensembles de U, et un entier 0 < k < jCj.
Question : Existe-t-il k éléments de C dont l’union soit égale à U.
Ce problème est NP-complet d’après [Kar72].
Remarque : Ensemble dominant et couverture par sommets sont des cas particuliers de couverture par ensemble. Dans le cas d’ensemble dominant, l’univers est l’ensemble des sommets, et la collection contient, pour chaque sommet du graphe, son voisinage clos. Dans le cas de la couverture par sommets, l’univers est l’ensemble des arêtes, et la collection contient, pour chaque sommet du graphe, l’ensemble des arêtes adjacentes à ce sommet.
Ensembles tropicaux
Dans cette section, nous allons considérer sur des graphes sommets-colorés, de façon non nécessairement propre. Une coloration d’un graphe peut avoir de nombreuses significations : dans un graphe représentant le web, la colora-tion d’une page pourra représenter sa thématique, dans le cas d’un graphe issu de l’étude du métabolisme d’une cellule en biologie, les couleurs peuvent correspondre à un type de réaction [FFHV11, LFS06], . . .
Une grande partie des travaux sur les colorations de graphe s’intéresse à savoir s’il est possible, étant donné un graphe non-coloré en entrée, d’at-tribuer une couleur à chacun des sommets de telle façon à ce que certaines propriétés soient observées, par exemple que deux sommets partageant la même couleur ne soient jamais trop proches l’un de l’autre [GJ79]. Ces tra-vaux correspondent à des modèles où la couleur représente quelque chose sur lequel les opérateurs ont au moins un certain contrôle ; un modèle classique étant la modélisation d’un ensemble d’émetteurs/récepteurs sans fils, où la couleur d’un sommet correspond à la fréquence qu’il utilise pour ses com-munications, et où l’on veut garantir qu’il n’y aura pas d’interférences entre les différents émetteurs en choisissant les fréquences intelligemment. Nous avons choisi d’étudier une situation différente où les couleurs représentent des caractéristiques des sommets que nous ne pouvons changer. Cette ap-proche est par exemple nécessaire pour traiter certains problèmes issus de la biologie, et plus précisément de l’étude du réseau métabolique d’une cellule. Le réseau métabolique est l’ensemble des nombreuses interactions chimiques qui peuvent avoir lieu entre les diverses molécules au sens d’une cellule : quelles molécules réagissent entre elles, agissent en tant que catalyseurs pour une réaction, ou au contraire comme inhibiteurs,. . . Une représentation pos-sible pour cet ensemble de données complexe est un graphe sommet-coloré. Un des problèmes issu de l’étude des réseaux métaboliques est la recherche de motif. Dans la recherche de motif, on reçoit en entrée un graphe dont les sommets sont colorés, et un motif (c’est-à-dire un ensemble de couleurs, avec une cardinalité pour chaque couleur). L’objet du problème est de trouver un ensemble de sommets connexes dont les couleurs sont exactement celles du motif. Ainsi, si le motif est {{rouge,2},{bleu,1}{vert,3}}, il s’agira de trouver un ensemble de 6 sommets exactement, connexe, contenant 3 sommets verts, deux sommets rouges et un sommet bleu. Ce problème est NP-complet, et le reste même avec de fortes restrictions sur les entrées possibles. Notamment, ce problème reste NP-complet même si l’on restreint les entrées aux arbres de degré maximum 3 et les motifs à des ensembles de couleurs tous de cardi-nalité 1, et de même si l’on restreint les entrées aux graphes bipartis de degré maximum 4, et aux motifs contenant exactement deux couleurs[FFHV11].
Nous allons présenter la notion d’ensembles tropicaux, c’est-à-dire d’en-sembles qui contiennent, pour chaque couleur utilisée dans la coloration du graphe, au moins un sommet de cette couleur. Tout d’abord, nous allons nous intéresser au problème de la recherche du plus petit ensemble connexe tropical, qui se rapproche du problème de recherche de motif. Puis, nous al-lons étudier la recherche d’un ensemble dominant tropical de taille minimum. L’article [CCK+14] propose des algorithmes exacts pour trouver le plus petit ensemble connexe tropical, dont le temps d’exécution est exponentiel.

Table des matières

1 Introduction 
2 Notations et définitions 
2.1 Graphes
2.2 Graphes sommet-colorés
2.3 Théorie des jeux
2.4 Complexité
2.5 Liste de problèmes utilisés pour les réductions dans la suite
3 Ensembles tropicaux 
3.1 Sous-graphes connexes tropicaux minimum
3.1.1 NP-complétude
3.1.2 Solvabilité à paramètre fixé (algorithme FPT)
3.1.3 Bornes supérieures
3.2 Dominants tropicaux minimum
3.2.1 NP-complétude
3.2.2 Approximations
3.2.3 Solvabilité à paramètre fixé (algorithme FPT)
3.2.4 Bornes supérieures
3.3 Autres ensembles tropicaux
4 Jeux de défense 
4.1 Introduction
4.2 Modèle général
4.3 Modèle des arêtes
4.4 Modèle des chemins
4.5 Autres modèles
5 Conclusion

Télécharger le rapport complet