Presentation

Le thème AGC est centré sur l’algorithmique des graphes et des treillis. Les principales orientations sont les algorithmes d’énumération, algorithmique des treillis et des familles de Moore, les décompositions et parcours de graphes et applications en fouille de données. Les membres de ce thème collaborent et co-publient avec les membres du thème DSI de l’axe SIC sur des problèmes liés à l’intégration de données et à la composition de services web (décidabilité et complexité).
Les résultats obtenus par ce thème lors des 4 dernières années se synthétisent comme suit :

• Enumération output-sensitive : Il s'agit de lister dans les hypergraphes des sous-ensembles de sommets/arêtes vérifiant une certaine propriété et seulement ces derniers, mais on veut que le temps d'exécution soit polynomial en la taille de la sortie. C'est un problème crucial en fouille de données. Des exemples incluent l'énumération des cliques maximales (des communautés dans des réseaux sociaux) ou des dominants minimaux (des ensembles qu'ils suffisent de connaître pour diffuser des rumeurs) dans un graphe. Le fait marquant est que nous avons montré que le problème d’énumération des dominants minimaux d’un graphe et l’énumération des transversaux minimaux d’un hypergraphe sont deux problèmes polynomialement équivalents [ACL-RI-1-128, C-ACTI-LN-1-37]. Ce dernier est un problème central dans plusieurs domaines (fouille de données, dualisation des fonctions monotones) et a été abordé en partie dans l’ANR DAG-09-13 regroupant des équipes de fouille de données et de SAT [COS-1-32, C-ACTI-LN-1-32]. Ce résultat inattendu, nous permet d’introduire la notion de dualité faible entre objets combinatoires et de montrer qu’on peut réutiliser les algorithmes d’énumération avec la même complexité si le gap est polynomial [ACL-RI-1-128,COS-1-31]. Cette dualité peut être considérée comme la réduction polynomiale entre les problèmes d’énumération qui semble difficile à définir par rapport à la réduction classique pour les problèmes de décision ou du comptage.

Nous espérons utiliser les propriétés de graphes pour répondre à la question de savoir si l’énumération des transversaux est polynomiale dans la taille de la donnée et la sortie. Ce travail s’effectuera dans le cadre de l’ANR GRAPHEN 2015-2019. Nous avons également analysé certains outils utilisés dans la littérature pour des problèmes d'énumération et avons introduit de nouvelles techniques qui semblent prometteuses car elles nous ont permis de résoudre certaines questions, en particulier l'énumération des arêtes dominants minimaux dans les graphes [C-ACTI-LN-1-56].

• Décomposition et parcours de graphes : En théorie des graphes la technique la plus fructueuse pour caractériser/classifier les graphes est la notion de décomposition de graphes. En général ces décompositions sont associées à des paramètres de graphes qui lorsqu'ils sont petits permettent de résoudre des problèmes difficiles en temps polynomial. Par conséquent il est intéressant de pouvoir calculer pour un graphe donné une décomposition qui minimise la largeur. Parmi les décompositions connues la décomposition en rang (linéaire) [C-ACTI-LN-1-13,ACL-RI-1-147] est l'une des plus intéressantes et intrigantes au vu de ses connexions avec la théorie des mineurs de Robertson et Seymour et des (Delta-)matroides, ces derniers introduits dans les travaux de Bouchet pour la caractérisation de la notion d'algorithme glouton. Nous avons initié la recherche sur le calcul de la largeur de rang linéaire de classes de graphes pour une meilleure compréhension des classes de graphes de largeur de rang (clique) bornée. Nous espérons bientôt une borne sur la taille des obstructions à la largeur de rang linéaire et également un algorithme pour calculer la largeur de rang (clique) linéaire des graphes de largeur de rang (clique) bornée. Des premiers résultats ont été obtenus, en particulier de une caractérisation de la largeur de rang linéaire des distance-héréditaires, ce qui a permis de donner la liste des graphes distance-héréditaires qui sont obstructions pour la largeur de rang et également un algorithme polynomial pour calculer la largeur de rang linéaire des distance-héréditaires [C-ACTI-LN-1-49].

Nous nous intéressons aussi au clique-separateur décomposition et aux parcours de graphes (LexBFS). En utilisant cette décomposition et LexBFS, nous avons obtenu un algorithme quadratique pour reconnaître les HD-graphes et l’identification des triangulations minimales.

• Algorithmique des treillis : Nous avons exploiter l’un des point fort du thème sur la théorie des treillis pour nous attaquer à la conjecture de Frankl « Toute famille fermée par union (famille de Moore) possède un élément qui appartient à plus de la moitié de la famille ». Nous avons réussi à dénombrer ces familles pour n=7 [C-ACTI-LN-1-11] et caractériser une décomposition récursive [ACL-RI-1-126] ainsi que le graphe biparti dont les bicliques sont en bijection avec ses familles.

• Nous avons aussi contribué à la conjecture de Chen-Chvátal sur le nombre de droites distinctes définies par un espace métrique discret.

• En collaboration avec le thème DSI de l’axe 2, Orange et la chaire industrielle auvergne-Orange, nous avons poursuivi les travaux sur la composition des services web pour considérer le cas de la présence des données (thèses L. Akroun et K. Ennaoui), ce qui nous permet d’identifier une nouvelle technique algorithmique basée sur la partition du domaine. Nous nous sommes aussi intéressés à la confiance numérique dans le web (thèse D. Dia) [C-COM-I-1-28, C-COM-I-1-23]. Ces travaux vont se poursuivre dans le cadre de la chaire industrielle sur la confiance numérique et en liaison avec le DIS 4 (Domaine d’Innovation Stratégique) de la S3 (stratégie de spécialisation intelligente) de la région Auvergne (financement d’une thèse sur ce sujet qui démarre en septembre 2015).

Le thème Algorithmique, Graphes, Complexité participe également dans des projets transversaux d’exploration tels que les prjets PETASKY (programme Mastodons de la mission à l’interdisciplinarité du CNRS) et BIGEARTHSKY (projet européen de type COST). Dans ce cadre, nous nous intéressons à la factorisation de matrices et au clustering, deux problèmes qui en terme d’ordres partiels correspondent respectivement au plongement dans un plus petit espace ou à la réduction de la dimension.