Apparaît également dans la collection : ALEA Days 2017 / Journées ALEA 2017
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que (1) le multi-ensemble des couleurs de V' correspond à M, (2) le sous-graphe G' induit par V' est connexe. Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique. Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique. Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
De Margaux Zaffran
De Laure Saint-Raymond
De Céline Duval
De Céline Duval
De Olivier Benoist
