1er sujet de recherche : Etude algorithmique de graphes arête-coloriés

 

Le sujet porte sur l’exploration algorithmique de graphes dont les arêtes sont coloriées par c>1 couleurs, pour c donné. Soit un graphe G(V,E) avec un ensemble de sommets G(V) et un ensemble d’arêtes E(G).  Soit maintenant  c une coloration des ses arêtes, i.e., une application de E(G) dans un ensemble C de couleurs de taille c. Nous disons que un sous-graphe G’ de G est proprement colorié si deux arêtes adjacentes dans G’ sont de couleurs distinctes. A  partir d’un graphe dont les arêtes sont coloriées par c couleurs, nous cherchons à extraire de sous-graphes avec de propriétés spécifiques sur la coloration des arêtes. Par exemple, cycles hamiltoniens dont deux arêtes adjacentes du cycle ayant de couleurs différentes, parcours euleriens sans deux arêtes consécutives monochromatiques, arbres couvrants proprement coloriés etc. Lorsque les arêtes du graphe initial sont coloriées rouge et bleu, nous appelons de tels cycles et chaînes « alternés », la propriété d’alternance ayant la signification que les arêtes sont coloriées alternativement  rouge/bleu/rouge…etc.

 

Motivation

Une telle étude est motivée par des nombreuses applications :

a.      Carrés latins et cycles alternés. Dans [1], l’auteur ramène le problème de la recherche d’un carré latin à un problème de cycle hamiltonien alterné dans un graphe complet arête colorié.

b.      Transmission de messages dans un réseau ennemi. Supposons que l’on veuille transmettre un message à n personnes, avec la propriété que tout message reçu dans un code soit retransmis dans un code différent. Une telle transmission du message est-t-elle possible ?

c.        Simulation de structures ADN par de graphes 2-arête coloriés. Dans [6] un chapitre entier est consacré aux graphes arête coloriés et leurs applications en bio informatique, tandis que une série de problèmes ouverts est proposée.

d.      Tournois bipartis et graphes arête coloriés. Les tournois bipartis sont intimement liés aux graphes complets 2-arêt coloriés, car comme il a été observé dans [4], tout tournoi biparti peut être considéré comme un graphe complet 2-arête colorié.

 

 

Résultats connus

Il est facile de voir que le problème du cycle hamiltonien alterné dans un graphe arête colorié G quelconque est NP-complet pour chaque nombre de couleurs c fixé, c>1. Toutefois si le graphe G est complet et ses arêtes sont coloriées avec deux couleurs, alors une première caractérisation non constructive a été proposée à [3]. Selon le théorème de Bankfalvi et Bankfalvi un graphe 2-arête colorié possède un cycle alterné hamiltonien ssi a) il possède une couverture de ses sommets par des cycles sommet-disjoints alternés  et b) pour tout pair de sommets x et y, il existe un chemin alterné reliant x et y.  Dans [4], nous avons re-étudié ce problème du point de vue algorithmique, en exhibant un algorithme qui trouve un tel cycle en temps O(n2.5) où n est le nombre de sommets du graphe. Au passage nous avons déduit une procédure de  même complexité qui permet de trouver un circuit hamiltonien dans un tournoi biparti, étendant ainsi un résultat précédent de Manoussakis et Tuza. Plus tard,  un algorithme parallèle a été prouvé dans [2]. Dans une deuxième partie de nos travaux, nous démontrons que si un graphe possède un cycle alterné hamiltonien, alors il possède de cycles alternés de toute longueur pair 2=<m<=n, ce qui étend un résultat de Beineke et Little relatif au pan cyclisme des tournois bipartis hamiltoniens. De plus, en exploitant les lemmes de structures de résultats précédents, nous déduisons la formule exacte du nombre de graphes complets 2-arête coloriés contenant un seul cycle hamiltonien alterné généralisant ainsi un résultat obtenu par M. Manoussakis et Y. Manoussakis relatif au nombre de tournois bipartis contenant un seul circuit hamiltonien.

D’autres algorithmes et résultats mathématiques ont été établis concernant la connexité « alternée », les parcours euleriens, chemins hamiltoniens, arbres couvrants etc…

 

Perspectives et problèmes ouverts

La plupart de résultats obtenus jusqu'à maintenant concernent les graphes complets 2-arête coloriés.

Dans un premier axe de recherche, nous souhaitons généraliser ces résultats dans le cas de graphes complets dont les arêtes sont coloriées par au moins 3 couleurs. En particulier, nous souhaitons savoir si nos algorithmes efficaces pour deux couleurs restent polynomiaux ou les problèmes deviennent NP complets pour trois couleurs et plus. A titre d’exemple nous citons deux problèmes publiés dans [4] et qui pour l’instant reste ouvert :

 

Problème 1 [4]. Etant donné un graphe G complet dont les arêtes sont coloriées par au moins 3 couleurs, existe-t-il un algorithme polynomial pour trouver un cycle (chemin) hamiltonien   proprement colorié dans G?

 

Problème 2 [4]. Etant donné un graphe G complet dont les arêtes sont coloriées par 2 couleurs, existe-t-il un algorithme polynomial pour trouver un chemin hamiltonien   proprement colorié réliant deux sommets x et y donnés  dans G?

 

Dans un deuxième axe de recherche, nous souhaitons exploiter nos résultats et voir leurs applications possibles. Par exemple, le problème ci-après est cité dans le livre [6] motivé par de recherches en bio informatique et le calcul de motifs possibles d’ADN particuliers.

 

Problème 3 [3]. Etant donné un graphe G 2-arête-colorié, il y a t-elle une méthode qui permet de calculer le nombre de parcours euleriens alternés distincts dans G?

 

 

Références

1. L.D. Andersen, Long alternating cycles in properly edge colored complete graphs, Mathematica Scandinavia (1989) 5-14.

2. E. Bampis Y. Manoussakis, et Y. Milis  On the parallel complexity of the alternating hamiltonian cycle problem,  RAIRO on Operations Research 33(4) (1999) 421-437. 

3. M Bankfalvi et Z. Bankfalvi, Alternating hamiltonian circuit in two-colored complete graphs, Theory of graphs, Proceedingsof Colloque Tihany (1968)  11-18

4. A. Benkouar, Y. Manoussakis, V. Paschos, R.Saad  On the complexity of Hamiltonian and Eulerian problems in edge-colored complete graphs,  RAIRO Journal On Operations Research Vol. 30 No 4 (1996) 417-438.

5. P. Pevzner, Computational Molecular Biology: An Algorithmic Approach, The MIT Press, 2000.

 


2eme sujet de recherche : Etude algorithmique des jeux basés sur des modèles de graphes

 

La théorie algorithmique des jeux est une émanation de la théorie des probabilités et de l’algorithmique. Elle représente l'application des mathématiques à la description et à la résolution algorithmique des problèmes liés aux jeux selon un modèle  mathématique donné (matrice, graphe etc.).  C'est John Von Neumann qui est le père de la théorie des jeux, en démontrant en 1928 le théorème le plus important dans ce domaine (le théorème du minimax), et en écrivant en 1944 avec O.Morgenstern l'ouvrage référence sur le sujet La théorie des jeux et le comportement économique.

 

Les principales approches traditionnelles dans le domaine, concernent des systèmes centralisés dans lesquels les agents coopèrent afin de atteindre un but commun.  Avec l’arrivée d’Internet, il est  apparu nécessaire d’étudier un nouveau comportement d'agents avec des interactions contradictoires. Par exemple, un utilisateur normal d’Internet et un expéditeur de spam’s sont deux agents avec des objectifs opposés : le 1er souhaite minimiser le nombre de spams qu’il reçoit, tandis que le 2eme souhaite maximiser le nombre de spams à envoyer.  Les concepts utilisés pour modéliser de tels systèmes sans contrôle centralisé, sont ceux de l’équilibre de Nash et la mesure du rapport de coordination (ou prix de l'anarchie) [5]. Parmi tous les états possibles d’un jeu donné, l’équilibre de Nash est définie comme un état dans lequel aucun agent n'a intérêt à changer sa stratégie. Il est à noter que plusieurs états peuvent amener à une équilibre de Nash et par conséquent la solution obtenue n'est pas toujours unique et peut conduire à des performances plus ou moins bonnes. Le rapport de coordination est une mesure de qualité de l'équilibre de Nash obtenue.

 

Dans le cadre de cette étude,  nous  considérons un problème de sécurité sur un réseau modélisé par un graphe G [1]. Sur un tel jeu il y a deux types de joueurs, les attaquants (virus etc.) et les protecteurs (logiciels de protection etc.) . L’attaquant utilise une distribution de probabilité afin de choisir les nœuds du réseau à endommager. A l’opposé, le protecteur,  en utilisant une autre distribution de probabilité, choisit une partie du réseau (ie a sous graphe H de G)  à nettoyer. Dans un tel scénario, l’objectif de l’attaquant est de maximiser la probabilité d’échapper à un nettoyage possible tandis que l’objectif du protecteur est de maximiser le nombre de nœuds à nettoyer.

Ce type de jeu non coopératif a été étudié dans le cas où la partie du réseau considérée par le protecteur est une arrête ou un chemin ou un ensemble d’arrêtes [1-4], i.e., lorsque le sous graphe H de G est isomorphe à une arrête ou un chemin, ou un ensemble d’arrêtes dans G.  Ici nous proposons de généraliser les résultats obtenus dans [1-4], en considérant n’importe quel sous graphe H des familles de graphes G (graphes parfaits, planaires bipartis etc.).

 

 

Références

 

1. M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Graph-Theoretic Network Security Game", Proceedings of the First Workshop on Internet and Network Economics (WINE 2005), LNS Springer-Verlag, Hong Kong, December 2005, to appear.

2. M. Mavronicolas, P. Panagopoulou,  and P. Spirakis,  "Cost Sharing Mechanisms for Fair Pricing of Network Usage", Proceedings of the Dagstuhl Seminar on Algorithmic Aspects of Large and Complex Networks (Dagstuhl Seminar Series 05361), September 2005, to appear

 3. M. Mavronicolas, V. Papadopoulou, A. Philippou and P. Spirakis, "A Network Game with Attacker and Protector Entities", Proceedings of the 16th Annual International Symposium on Algorithms and Computation (ISAAC 2005), Lecture Notes in Computer Science Springer-Verlag, Sanya, Hainan, China, December 2005, to appear.

 4. R. Elsδsser, M. Gairing, T. Lόcking M. Mavronicolas and B. Monien "A Simple Graph-Theoretic Model for Selfish Restricted Scheduling", Proceedings of the First Workshop on Internet and Network Economics (WINE 2005), LNCS, Springer-Verlag, Hong Kong, December 2005, to appear

5. MJ. Osborne and A. Rubinstein, A course in Game Theory, MIT Press, 1994.