Thèse Couverture Minimale de Graphes par Familles Finies de Motifs Théorie Complexité et Algorithmes H/F - Université Paris-Saclay GS Informatique et sciences du numérique

Établissement : Université Paris-Saclay GS Informatique et sciences du numérique
École doctorale : Sciences et Technologies de l'Information et de la Communication
Laboratoire de recherche : Données Algorithmes pour une ville intelligente et durable
Direction de la thèse : Dominique BARTH
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-15T23:59:59

Le sujet de recherche abordé ici concerne une forme particulière de problèmes de couverture de graphes. Etant donnés un graphe G et un ensemble fini de graphes F={H1,...,Hp}, une couverture de G par F est un ensemble de sous-graphes partiel C={G1,..., Gk} de G tel que chaque Gi de C est isomorphe à un graphe de F et tel que pour chaque arête de G, il existe au moins un Gi de C qui la contienne; la taille d'une telle couverture est C . Le problème général au coeur de ce sujet consiste, étant donnés un graphe G et une famille finie F, à déterminer s'il existe une couverture de G par F et si oui, qu'elle en est la taille minimum. Ce problème de minimisation a été montré NP-complet dans le cas où F est l'ensemble (infini) des graphes bipartis complets. Il a été prouvé récemment au sein de notre laboratoire que ce problème est NP-complet quand G est quelconque et que F ne contient qu'une chaine de longueur 3.

L'objectif de ce projet doctoral est d'étudier ce problème pour différents types de familles F sous l'angle de la théorie des graphes, de la complexité algorithmique et de la résolution par optimisation combinatoire et/ou apprentissage automatique. Dans le paysage de la couverture de graphes par des sous-graphes déjà peuplé de nombreux résultats, la spécificité de ce sujet de thèse consiste notamment à considérer des types de graphes G particuliers et des familles spécifiques F de taille finie. En effet, une des applications de ce problème concerne par exemple des applications de dynamiques moléculaires, ce qui consiste en particulier à considérer que G est souvent un graphe planaire et que F contient un nombre limité de graphes spécifiques de taille bornée. L'un des premier cas à traiter sera d'étudier la complexité, puis la résolution du problème où G est un arbre et F ne contient qu'une chaine de longueur quelconque. Ce problème est conjecturé NP-complet, et dans cette hypothèse, des résultats en termes de d'approximabilité ou de complexité paramètrée sont envisageables. D'autres familles de graphes F seront ensuite considérées, comme par exemple des formes spécifiques d'arbres, en particulier des étoiles, puis des familles plus générales.

Les objectifs scientifiques de ce projet doctoral se décline ainsi dans différents domaines :
- Théorie des graphes : établir des propriétés structurelle garantissant l'existence de couverture pour des familles de graphes particulières. Cette étude devcra s'appuyer sur un état de l'art spécifique et complet des travaux existants.
- Complexité et classes polynomiales: identifier les familles F et classes de graphes G pour lesquelles le problème est polynomial ou NP-difficile, et étudier l'approximabilité et l'intractabilité paramétrée selon des paramètres naturels (taille de la couverture, treewidth, etc.).
- Algorithmes exacts et paramétrés : développer des algorithmes exacts pour des familles spécifiques de motifs et concevoir des heuristiques pour des instances structurées.
- Optimisation combinatoire et apprentissage automatique : définition et évaluation d'une part de méthodes exactes pour des instances spécifiques de taille limitée et d'autre part d'approches méta-heuristiques (notamment par voisinnage) pour des instances plus générales. Il s'agira aussi d'explorer l'apport de l'apprentissage par renforcement distribué, où chaque motif agit comme un agent autonome pour décider de son placement sur le graphe cible.

La couverture d'un graphe par des sous-graphes donnés constitue une problématique centrale en théorie des graphes et en algorithmique. Ce cadre général englobe plusieurs problèmes classiques : couverture d'arêtes, décompositions en cycles ou cliques, et H-cover. Ces sujets autour de la théorie des graphes, de la complexité et de la résolution sont au coeur du projet scientifique de l'équipe ALMOST du laboratoire DAVID au sein de laquelle sera réalisée cette thèse.

- Théorie des graphes : établir des propriétés structurelle garantissant l'existence de couverture pour des familles de graphes particulières. Cette étude devcra s'appuyer sur un état de l'art spécifique et complet des travaux existants.
- Complexité et classes polynomiales : identifier les familles F et classes de graphes G pour lesquelles le problème est polynomial ou NP-difficile, et étudier l'approximabilité et l'intractabilité paramétrée selon des paramètres naturels (taille de la couverture, treewidth, etc.).
- Algorithmes exacts et paramétrés : développer des algorithmes exacts pour des familles spécifiques de motifs et concevoir des heuristiques pour des instances structurées.
- Optimisation combinatoire et apprentissage automatique : définition et évaluation d'une part de méthodes exactes pour des instances spécifiques de taille limitée et d'autre part d'approches méta-heuristiques (notamment par voisinnage) pour des instances plus générales. Il s'agira aussi d'explorer l'apport de {l'apprentissage par renforcement distribué}, où chaque motif agit comme un agent autonome pour décider de son placement sur le graphe cible.

La/le candidat(e) doit être titulaire d'un diplôme de master ou d'ingénieur en informatique, avec une formation en théorie des graphes, en algorithmique et en complexité.