Diminution Optimale de PAramètres d'un GraphE – DOPAGE

De nos jours, un aspect fondamental dans le monde industriel est le concept de fiabilité. Cette notion est particulièrement cruciale dans certains domaines liés à la conception ou à la gestion de réseaux. Si l'on fournit des services payants à des clients, on doit s'assurer de pouvoir remplir sa part du contrat. On a donc le devoir d'anticiper tout événement susceptible d'entraîner une situation où on ne le peut pas. En d'autres termes, on doit être fiable. Ainsi, si on doit réaliser des tâches qui, d'une manière ou d'une autre, impliquent l'utilisation d'un réseau, alors on est amené à exiger que ce réseau fonctionne effectivement. Concevoir ou gérer des réseaux qui fonctionnent correctement semble donc être une chose essentielle. Quel type d'événements pourraient conduire un réseau à tomber en panne ? Si le réseau est un réseau de télécommunication (où chaque noeud est relié aux autres noeuds par des liens, et où les noeuds communiquent entre eux), certains liens peuvent tomber en panne, empêchant ainsi les autres noeuds de continuer à communiquer entre eux. Dans de telles situations, on doit s'assurer que le réseau va continuer à marcher dans une certaine mesure, ce qui signifie que la défection d'un seul noeud ou d'un seul lien ne doit pas entraîner une panne complète du réseau. En d'autres termes, on doit prendre ceci en considération quand on conçoit le réseau (mais aussi quand on définit la politique de routage). Les graphes sont des entités formelles particulièrement adaptées à la modélisation de différents types d'objets issus du monde réel, tels que les réseaux (les noeuds et les liens devenant des sommets et des arêtes, respectivement). De nombreux problèmes intervenant dans la conception de réseaux peuvent ensuite être traduits en termes de graphes, et étudiés à l'aide de puissants outils issus de la théorie (algorithmique) des graphes. Ainsi, la construction de réseaux fiables peut être vu la construction de graphes ayant des propriétés particulières. Un exemple standard est le suivant : on dit qu'un graphe est k-connexe si le nombre minimum de sommets (ou d'arêtes) que l'on doit retirer pour le déconnecter est au moins k. En outre, dans le cadre de cet exemple, on définit un graphe comme étant fiable si, lorsque une ou plusieurs pannes se produisent (sur des sommets ou des arêtes), les sommets suivants ont encore la possibilité de communiquer entre eux. Par conséquent, si on suppose qu'au plus k-1 sommets (ou arêtes) peuvent tomber en panne en même temps, alors un réseau (graphe) est fiable si et seulement si il est k-connexe. Cet exemple est classique ; néanmoins, il peut arriver que la notion de fiabilité adaptée à une application particulière ne soit pas celle-là. Supposons par exemple que l'on se donne un réseau dans lequel les noeuds (des ordinateurs) doivent travailler deux par deux pour une raison particulière : deux ordinateurs donnés ne peuvent travailler ensemble que si ils sont reliés par un lien (une arête), et aucun ordinateur ne peut travailler avec plus d'un autre ordinateur. On voudrait obtenir un nombre maximum de paires d'ordinateurs. En termes de graphes, ce problème n'est qu'un simple problème de couplage maximum. Or, comme précédemment, il peut arriver que certains sommets (ou certaines arêtes) tombent en panne. Dans ce cas, on veut déterminer l'impact d'un tel événement sur les performances du réseau. Si, par exemple, au plus f noeuds (ou arêtes) cessent de fonctionner en même temps, quelle est la plus petite valeur possible d'un couplage maximum dans le réseau obtenu ? Ou, pour parler en termes de fiabilité, peut-on garantir que, si f pannes se produisent simultanément, un nombre suffisant (au moins p) de paires d'ordinateurs vont continuer de travailler ensemble ? Ce problème a récemment été montré NP-complet, et donc "difficile" (alors que déterminer un couplage maximum dans un graphe est un problème "facile"). Néanmoins, il a aussi été démontré que plusieurs cas particuliers intéressants étaient "faciles". Ces résultats constituent une première étape dans l'étude de ce type de problèmes, étroitement liés à la notion de fiabilité. Il y a d'autres exemples intéressants de problèmes de ce type (ils seront développés dans le reste du projet), ce qui démontre que cette problématique est réellement émergeante. Pourtant, l'étude systématique et la classification de ces problèmes n'a pas encore été initiée. Par conséquent, l'objet du présent projet est de démarrer des investigations dans ce domaine de recherche. Comme cela implique une quantité très importante de moyens (ressources humaines et financières), notre ambition se limite à fournir une première approche à cette problématique, en considérant surtout les principaux problèmes associés à cette notion, en déterminant leur complexité et en concevant des algorithmes efficaces (exacts ou approchés) pour les résoudre, et, finalement, en esquissant un cadre commun pour résoudre tout problème de ce type.