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.