Forum 'Stages' - Sujet créé le 2026-01-15 par Dimitri Watel
Bonjour à tous
Vous trouverez ci-dessous une offre de stage de fin d'études. Nous recherchons un(e) étudiant(e) pour un stage de niveau M2 au sein du laboratoire CEDRIC du CNAM de Paris pour travailler sur un problème d'études de bases de cycles dans les graphes temporels - soit sur des aspects théoriques de complexité et d'approximabilité, soit sur des aspects d'évaluation de performances d'algorithmes.
Nous recherchons un profil avec des connaissances en programmation, en théorie des graphes, en algorithmique de graphes et en recherche opérationnelle.
Candidature : prendre contact en envoyant un CV et des relevés de notes à dimitri.watel@ensiie.fr, cedric.bentz@cnam.fr et christophe.picouleau@cnam.fr
N’hésitez pas à diffuser cette offre auprès des étudiant(e)s potentiellement intéressé(e)s.
Cordialement
Dimitri Watel
=================
Complexité du problème d’intersection maximum de bases de cycles de poids minimum
Mots clefs : Théorie des graphes, Algorithmique de graphes, Programmation avec des bibliothèques
de graphes, Base de cycles minimum, (Intersection de matroı̈des, Complexité algorithmique, Com-
plexité paramétrée, Approximabilité)
Ces travaux sont financés par la FMJH au travers du projet PGMO MINCY-INTEGRALITY.
Résumé du travail à effectuer
Dans ce stage, nous étudions un problème d’optimisation dans les graphes, en particulier dans
les graphes dynamiques. Une application possible se situe dans le domaine chémo-informatique.
Un graphe temporel sera ici un graphe dont l’ensemble des arêtes évoluent dans le temps. Le
problème étudié consiste, connaissant un graphe temporel, à rechercher des cycles représentatifs
des différentes itérations du graphe de sorte à maximiser le nombre de cycles choisis présents dans
toutes les itérations du graphe.
Le travail sur ce sujet peut se découper en plusieurs parties, en fonction des compétences et de
l’intérêt du ou de la stagiaire :
— une partie théorique - l’objectif étant d’étendre des résultats de complexité ou d’approxima-
bilité du problème dans le cas où le graphe temporel vérifie des contraintes structurelles (par
exemple si le degré maximum du graphe ne dépasse jamais 3).
— une partie pratique - l’objectif étant de programmer des algorithmes exacts, approchés ou
heuristiques sans garantie pour résoudre le problème, soit dans le cas général, soit dans des
cas particuliers qui auraient des propriétés intéressantes pour faciliter la résolution.
Il est également possible d’envisager des variantes du problème étudié.
Définition du problème étudié
Dans un graphe simple non orienté, une base de cycles est un ensemble minimum de cycles
capable de générer tous les autres. On utilise ici pour les cycles une définition très générale : un
cycle est un graphe dont les nœuds sont de degré pair. Ainsi deux cycles élémentaires disjoints
forment un cycle, et un graphe eulérien est également un cycle. On définit une opération d’addition
⊕ sur les cycles : connaissant deux cycles c1 et c2 , le cycle c1 ⊕ c2 consiste à garder les arêtes de
c1 ∪ c2 qui ne sont pas dans c1 ∩ c2 . La Figure 1 donne des exemples de cycles et d’addition de
cycles.
On dit qu’un ensemble de cycles C génère un cycle d si c∈C c = d. Une base de cycles est un
ensemble minimum de cycles qui génèrent tous les autres avec cette définition. Une base de poids
minimum est une base de cycle dont la somme des tailles des cycles est minimum.
Trouver une base de cycles minimum pour un graphe peut se faire en temps polynomial, par
exemple avec l’algorithme de Horton [3]. On s’intéresse ici à trouver des bases dans plusieurs graphes
en maximisant l’intersection des bases choisies :
Problème 1 (max-MCBI). Soient (G1 , G2 , . . . , Gk ) des graphes ayant les mêmes nœuds, trouver Tk un sous-ensemble de cycles B de i=1 Gi de taille maximum tel que, pour tout i ∈ [1; k] il existe
une base minimum Bi de Gi telle que B ⊆ Bi.
Cette étude s’inscrit dans le cadre d’étude de trajectoires de conformations moléculaires. La
trajectoire représente la succession d’apparitions et de disparitions de liaisons faibles au cours du
temps. Les bases de cycles minimums font partie des propriétés structurelles des molécules capables
de caractériser certaines propriétés chimiques [1, 2]. Nous étudions la capacité de la similarité entre
les base minimums des conformations d’une trajectoire à caractériser de telles propriétés. Ce stage
se concentre uniquement sur notre capacité à résoudre le problème max-MCBI.
Références
[1] Ylène Aboulfath, Dominique Barth, Thierry Mautor, Dimitri Watel, and Marc-Antoine Weisser.
Polymorphic cycle basis in a sequence of graphs to analyze the structural evolution of a molecular
dynamic trajectory. In Petra Mutzel and Nicola Prezza, editors, 23rd International Symposium
on Experimental Algorithms, SEA 2025, July 22-24, 2025, Venice, Italy, volume 338 of LIPIcs,
pages 1 :1–1 :14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
[2] Ylène Aboulfath, Sana Bougueroua, Alvaro Cimas, Dominique Barth, and Marie-Pierre Gai-
geot. Time-resolved graphs of polymorphic cycles for h-bonded network identification in flexible
biomolecules. Journal of Chemical Theory and Computation, 20(3) :1019–1035, 2024.
[3] J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM
Journal on Computing, 16(2) :358–366, apr 1987.
Déroulement et détails pratiques
Le niveau du ou de la stagiaire attendu est celui d’un BAC+5 avec des connaissances en programmation, en théorie des graphes, en algorithmique de graphes et en recherche opérationnelle. La personne retenue sera accueillie soit dans les locaux du CNAM à Paris dans le laboratoire CEDRIC ou de l’ensIIE à Evry. Son encadrement au jour le jour sera effectué par Dimitri Watel, Cédric Bentz et Christophe Picouleau.
La durée du stage sera d’environ 5 mois, sur la période de fin d’études 2026 (avant, pendant ou
après l’été 2026).
Contact
Dimitri Watel, Maı̂tre de conférences de l’ensIIE (Evry), laboratoire CEDRIC-CNAM, dimitri.watel@ensiie.fr
Cédric Bentz, CNAM Paris, laboratoire CEDRIC-CNAM, cedric.bentz@cnam.fr Christophe Picou-
leau, CNAM Paris, laboratoire CEDRIC-CNAM, christophe.picouleau@cnam.fr