AlGCo : algorithmes, graphes et combinatoire
Stages M2 Recherche L'équipe AlGCo propose chaque année plusieurs stages à destinations des étudiants de Master 2 Recherche. N'hésitez à nous contacter pour obtenir de plus amples informations. Archives 2014-2015 Complexité paramétrée et complétion plane à diamètre borné.
Encadrants : Dimitrios M. Thilikos
Sujet attribué à Clément Requilé
L'objectif de ce stage est le design de différents algorithmes FPT pour résoudre le problème de la completion de graphe plans à diamètre borné.
Présentation détaillée ici. Etude des Schnyder woods dans les graphes sur les surfaces
Encadrants : Benjamin Lévêque
Sujet attribué à Ahmed Rafik
Une ”Schnyder wood” est une orientation et coloration des arêtes internes d’un graphe triangulé planaire vérifiant une jolie propriété locale. Nous proposons une généralisation de cette structure aux graphes triangulés sur les surfaces orientées de genre quelconque : sphère, tore, double tore, bretzel, etc. Le but de ce stage est d’étudier de manière appronfondie le cas du double tore.
2013-2014 Algorithmes FPT et noyaux dans les graphes sans sous-graphes induits.
Encadrants : Ignasi Sau
Sujet attribué à Henri Perret du Cray
L'objectif de ce stage est de réaliser une étude paramétrée de
problèmes définis dans les classes de graphes qui excluent un graph
fixé H en tant que sous-graphe induit, pour des cas particuliers du
graphe H.
2012-2013 Sommet-arboricité dans les graphes planaires.
La sommet-arboricité d'un graphe G est le nombre minimum k tel qu'on peut partitionner l'ensemble des sommets de G en k sous-ensembles induisant chacun une foret.
Pour les graphes planaires, la sommet-arboricité est au plus 3 et cette borne est atteinte.
Un papier récent de Harutyunyan et Mohar montre, en particulier, que tout graphe planaire admet au moins 2^(n/9) décompositions distinctes en 3 forets. En utilisant le resultat de Borodin que les graphes planaires ont une coloration acyclique avec au plus 5 couleurs, on obtient facilement une borne inférieure de 2^(n/5). L'étudiant devra tenter d'améliorer encore cette borne. On pourra s'intéresser à d'autres problemes voisins:
Extension du théorème d'exclusion des graphes planaires
Encadrant : Dimitrios Thilikos
Sujet attribué à Jean-Florent Raymond
Un des résultats les plus influents de la Théorie du Mineurs de Graphes
est le théorème d'exclusion des graphes planaires. L'objectif de ce stage
est d'étudier les méthodologies et les applications de ce théorème et de travailler
sur d'éventuelles extensions, généralisations et améliorations.
Kernelization et matroïdes
Encadrant : Christophe Paul
Sujet attribué à Margaux Nattaf
Issue de la théorie de la complexité et des algorithmes paramétrés, la kernelization offre un cadre théorique permettant de formaliser et mesurer l'efficacité des méthodes de réduction ou prétraitement des données. Il s'agit de déterminer si en temps polynomial, il est possible de réduire "significativement" une instance d'un problème réputé difficile (NP-Complet). L'instance réduite, appelée noyau, est une instance équivalente à l'instance initiale. L'efficacité de la réduction est alors mesurée en fonction d'un paramètre indépendent de la taille de l'instance initiale.
Les progrès observés ces dernières années dans ce domaine sont impressionnants. Outre de nouvelles techniques algorithmiques en général issue de la théorie des graphes, nous noterons en particulier les nouveaux outils permettant d'établir des bornes inférieures sur la taille des noyaux et des outils logiques permettant d'établir des méta-théorèmes capturant un grand nombre de problèmes. Récemment, de nouveaux résultats positifs (noyaux polynomiaux) ont été obtenus grâce à l'utilisation de la théorie des matroïdes. Nous proposons dans un premier temps de mener un étude bibliographique des résultats impliquant les matroïdes dans le cadre de la kernelization et plus largement la complexité paramétrée. Par la suite, le stage pourra s'orienter de plusieurs manières:
Algorithmes efficaces à paramètre fixé dans des classes de graphes particulières
Encadrant : Ignasi Sau
Sujet attribué à Julien Baste
Dynamic programming over tree decompositions is one of the most
powerful and widely used techniques to solve hard graph problems. In
this setting, a natural parameterization is to consider the tree-width
tw of the input graph, whose algorithmic importance dates back to
Courcelle's theorem, stating that graph problems expressible in MSOL
can be solved in f(tw).n steps. This implies that a large number of
graph problems are FPT when parameterized by the tree-width of their
input graph. As the bounds for f(tw) provided by Courcelle's theorem
are huge, the design of dynamic programming algorithms for specific
problems so that f(tw) is a "simple" function became a natural
ingredient for many results on graph algorithms. According to
well-known complexity results, for many problems the best function
f(tw) that we can hope for is a single-exponential one, that is, of
the form f(tw)=2^O(tw).
In the last years single-exponential algorithms have been provided for a number of problems in the case when the input graph is sparse, and it was an important open question whether single-exponential algorithms for the same family of problems exist also on general graphs. A positive answer to this question has been recently been given by the randomized algorithm of Cygan et al. [arxiv.org/abs/1103.0534, FOCS 2012] and by the deterministic algorithms of Bodlaender et al. [arxiv.org/abs/1211.1505]. But this is not the end of the story, as many interesting questions remain to be investigated. For instance, one of the objectives of this internship is whether the (optimal) running times of some of the single-exponential algorithms presented in the abovementioned papers for general graphs can be improved in the case where the input graph is sparse. Présentation détaillée ici. 2011-2012 Implications entre orientations de triangles ou de tétraèdres
Encadrant : Emeric Gioan
Sujet attribué à Guillaume Guégan
On appelle chirotope l'orientation (c'est un signe + ou -) d'un triangle (en 2D) ou d'un tétraèdre (en 3D). L'ensemble des chirotopes d'un ensemble donné de points satisfait des règles algébrico/combinatoires connues. Ici, on connait une partie A de l'ensemble des chirotopes. On cherche à calculer algorithmiquement quel sous-ensemble plus grand est impliqué par cet ensemble A, en suivant les règles, ainsi qu'un sous-ensemble plus petit qui impliquerait l'ensemble A.
Présentation détaillée ici. Polynomial kernels for variants of domination problems in planar graphs
Encadrant : Ignasi Sau
Sujet attribué à Valentin Garnero 2010-2011 Le problème d'acquisition de données pour une torpille en immersion
L'étude du problème d'ordonnancer des tâches-couplées soumises à des contraintes de compatiblité est motivée par le problème d'acquisition de données par une torpille en immersion. En effet, la torpille possède des capteurs qui collectent des informations qui sont alors traitées sur un monoprocesseur. Une sonde émet une onde qui se propage sous l'eau pour recueillir des données, appelée tâches d'acquisition. Ainsi, nous aurons deux sous-tâches : une qui envoie l'écho, l'autre qui le reçoit et un temps d'inactivité incompressible et indilatable entre les deux sous-tâches qui représente la propagation de l'écho sous l'eau. Les tâches d'acquisition peuvent être assimilées à des tâches-couplées. Pendant ce temps d'inactvité, nous pouvons envoyer d'autres échos sur d'autres sondes afin d'employer le temps d'inactivité. Cependant, la localisation trop proche des ondes provoqu! ent des perturbations et des interférences. Sachant que nous souhaitons traiter des informations exemptes d'erreur, nous construisons un graphe dit de compatibilité entre les tâches. Ce graphe décrit l'ensemble des tâches pouvant potentiellement exécuter au moins une sous-tâche durant la période d'inactivité d'une autre. Les informations récoltées via le retour de l'écho sont traitées par le monoprocesseur engendrant un traitement par le processeur. Ces tâches, dites de traitement, sont des successeurs des tâches d'acquisition.
Nous étudierons le problème du point de vue de la théorie de la complexité et de l'approximation. Nous tenterons de classifier les problèmes selon le critère de l'existence ou non d'un algorithme polynomial. De plus, dans le cas où le problème est NP-complet, nous souhaitons développer des algorithmes efficaces (ayant un ratio de performance relative le plus faible possible). Nous étudierons dans un premier temps des graphes de compatibilité structuré (biparti, arbre, .....) Propriétés structurelles de graphes via des méthodes de déchargement global
Un certain nombre de problèmes de théorie des graphes peuvent se résoudre à l'aide de procédures de déchargement. Le principe est le suivant : (1) des charges sont assignées à certains éléments d'un graphe, (2) une phase de déchargement permet de répartir les charges sur les éléments du graphe, (3) un bilan des charges permet de montrer la propriété souhaitée.
Cette technique de preuve intervient dans de nombreux résultats, dont le plus célèbre est le Théorème des 4 Couleurs. Lors de l'étape (2), la répartition des charges se fait très souvent de manière locale (les éléments adjacents échangent de la charge). En 2005, Borodin a fait évoluer cette technique en introduisant des règles de déchargement global, i.e. des éléments arbitrairement éloignés s'échangent de la charge. À ce jour, peu de résultats utilisant le déchargement global ont vu le jour, mais la technique est prometteuse. Il faudra dans un premier temps lire les quelques papiers qui utilisent cette nouvelle technique de preuve afin de d'approprier la méthode. Par la suite, nous choisirons quelques résultats sur lesquels nous pourrons travailler (améliorer les bornes inférieures/supérieures, transformer un déchargement local en global, ...). Bornes inférieures pour la kernelization (méthodes et outils)
Encadrant : Christophe Paul
Sujet attribué à Rémi Watrigant
La complexité paramétrée offre un cadre théorique et algorithmique pour l'étude et la résolution
exacte de problèmes NP-difficile. L'idée générale est de déterminer si le coût exponentiel inhérant
à la résolution d'un problème peut-être borné par une fonction d'un paramètre k indépendant de la taille n
de la donnée: existe-t-il un algorihme de complexité f(k).poly(n) ?
L'existence d'un algorithme paramétré est équivalent à l'existence d'un algorithme de kernelization, c'est à dire, une réduction polynomiale en une instance équivalente dont la taille est bornée par une fonction g(k) dépendant uniquement du paramètre k. La question est alors de savoir si la fonction g() peut-être polynomiale ou non. Depuis quelques années, des outils ont été développés et permettent de montrer qu'il est peu problable que certains problèmes paramétrés admettent un kernel polynomial. Le but du stage est, après une étude bibliographique de l'état de l'art, d'étendre ces techniques ou les appliquer à des problèmes paramétrés de graphes pour lesquels aucune borne n'est connue. Bibliographie: [1] Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin: On Problems without Polynomial Kernels (Extended Abstract). ICALP (1) 2008: 563-574 [2] Hans L. Bodlaender, Stéphan Thomassé, Anders Yeo: Kernel Bounds for Disjoint Cycles and Disjoint Paths. ESA 2009: 635-646 [3] Michael Dom, Daniel Lokshtanov, Saket Saurabh: Incompressibility through Colors and IDs. ICALP (1) 2009: 378-389 [4] Hans L. Bodlaender, Bart M. P. Jansen, Stefan Kratsch: Cross-Composition: A New Technique for Kernelization Lower Bounds CoRR abs/1011.4224: (2010) Complexes Cellulaires sans Entrelacs
Encadrant : Daniel Gonçalves
On dit d'un graphe qu'il est sans entrelacs (linkless embeddable) si il admet un plongement dans R3 sans que deux cycles disjoints ne soient entrelacés. On observe par exemple que tout graphe planaire ou tout graphe apex (un graphe G, tel que G\v est planaire, pour un sommet v donné) admet une telle représentation, et est donc sans entrelacs.
Cette classe de graphes est intéressante par la place qu'elle a dans la hiérarchie induite par le paramètre de Y. Colin de Verdière, µ(G). Ce paramètre qui est un entier positif définit par les propriétés spectrales de certaine matrices associées à G, redéfinit de façon surprenante plusieurs classes de graphes topologiques. En effet:
Pour un graphe G, planaire ou apex, on sait construire un sous-complexe de C2(G), D2(G), qui admet un plongement dans R3 sans intersections (notamment entre disques) et qui induit un plongement plat de C2(G). Ce complexe D2(G) qui est relativement petit (au plus 5|V(G)| disques) permet de manipuler ces graphes algorithmiquement. Le but de ce stage est donc de généraliser la construction de D2(G) à tous les graphes sans entrelacs. Réaliseurs et Partition de Sommets
Encadrant : Daniel Gonçalves
Sujet attribué à Yasser Kaddour
Un graphe est planaire si il admet une représentation dans le plan sans croisement d'arêtes. Un graphe est planaire externe si il admet une représentation planaire dans laquelle tous les sommets sont sur la face externe.
Il existe différentes preuves des propriétés suivantes:
Il est simple de constater qu'un graphe est une forêt de chemins si et seulement si il admet un 2-réaliseur. En 1989 W. Schnyder a prouvé un théorème surprenant : un graphe est planaire si et seulement si il admet un 3-réaliseur. Plus récemment, S. Felsner et W.T. Trotter ont montré qu'un graphes est planaire externe si et seulement si il admet un 3-réaliseur dont les ordres <1 et <2 sont opposés lorsqu'on les restreints à V. Le but de ce stage est dans un premier temps de reprouver les propriétés (P1), (P2) et (P3) en utilisant les réaliseurs de graphes. Une généralisation naturelle d'un tel résultat serait de montrer que les graphes ayant un k-réaliseur admettent des partitions de leur sommets en t-réaliseurs, pour t<k. |