Recherche

La complexité paramétrée mesure la complexité d'un algorithme décidant un problème en fonction de la taille de l'entrée et d'un paramètre associé au problème, noté k. Ce paramètre peut prendre diverses formes, attendu qu'il soit petit par rapport à la taille de l'entrée n. Dans ce contexte, l'objectif est de décider si un problème peut être décidé avec une complexité de la forme f(k) . poly(n), où f est une fonction calculable, exponentielle en k si le problème considéré est NP-Complet. Un tel problème est alors dit FPT, pour Fixed-Parameter Tractable.

Dans le cadre de la l'algorithmique des graphes, un des exemples classiques est Vertex Cover où l'objectif est de décider si le graphe peut être couvert en utilisant au plus k sommets : toute arête du graphe doit avoir une de ses extrémités dans cet ensemble de k sommets. Ce problème admet un algorithme simple s'exécutant en temps 2^k . poly(n), ce qui améliore l'algorithme "naïf" consistant à énumérer toutes les solutions possibles, de taille au plus k.

Une définition équivalente est la notion d' algorithmes de noyau, qui formalise la technique classique de pré-traitement : un noyau pour un problème paramétré est un algorithme polynomial qui transforme une instance (I,k) en une instance équivalente (I'.k') dont la taille est bornée par une fonction de k. L'objectif est d'obtenir une fonction polynomiale en k, tout algorithme FPT admettant de fait un noyau exponentiel.

De nombreux problèmes paramétrés admettent des noyaux polynomiaux mais il est prouvé que ce n'est pas toujours possible, sous certaines hypothèses de complexité. Poursuivant les travaux initiés en thèse, nous essayons de caractériser les problèmes de modifications d'arêtes admettant un noyau polynomial, en particulier pour des sous-classes de graphes triangulés.

Un graphe a une structure de communautés si ses nœeuds peuvent être groupés (dans une partition ou des ensembles chevauchants) de telle sorte que les nœeuds au sein d'un même groupe sont densément connectés. De (très) nombreux algorithmes sont capables de détecter des communautés au sein d'un graphe, éventuellement valué...

... et bien souvent non orienté ! En effet, de nombreux algorithmes semblent considérer l'orientation entre deux nœuds d'un réseau comme une information négligeable et recommandent donc de l'ignorer. Avec Nicolas Dugué nous avons montré que négliger l'orientation en utilisant l'algorithme de Louvain pouvait résulter en une perte d'information. Nous avons donc proposé une implémentation orientée de cet algorithme, disponible ici.

La notion d' embeddings de nœeuds (à ne pas confondre avec le plongement de graphes) consiste à associer à chaque sommet d'un graphe un vecteur à valeurs réelles, de petite dimension, tout en préservant certaines propriétés structurelles du graphe (voisinages, structure de communautés, ...). Cette approche, inspirée de techniques du traitement automatique du langage naturel, consiste la plupart du temps à essayer d'obtenir des vecteurs de petite dimension, quitte à perdre en interprétabilité. Nous avons proposé une méthode prenant le contre-pied de cette direction et utilisant les structures de communautés des graphes du réel pour proposer une représentation dans une dimension (relativement) plus grande mais creuse et interprétable. Cet outil est disponible ici.