Ces travaux sont financés par la FMJH au travers du projet PGMO MINCY-INTEGRALITY.

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\oe{}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 $\oplus$ sur les cycles : connaissant deux cycles $c_1$ et $c_2$, le cycle $c_1 \oplus c_2$ consiste à garder les arêtes de $c_1 \cup c_2$ qui ne sont pas dans $c_1 \cap c_2$. On dit qu'un ensemble de cycles $C$ génère un cycle $d$ si $\bigoplus_{c \in C} c = d$. Muni de l'opérateur $\oplus$ et du corps $\mathbb{Z} / 2\mathbb{Z}$, l'ensemble $C$ forme un espace vectoriel dont la dimension est le nombre cyclomatique $\mu(G) = m - n + p$ où $m, n$ et $p$ sont respectivement le nombre d'arêtes, de n\oe{}uds et de composantes connexes de $G$. Une base de cycles est une base de cet espace vectoriel. 

On s'intéresse dans cette présentation aux base minimums. Chaque cycle est associé à un poids égal à sa taille, une base minimum est une base de cycles dont la somme totale des poids 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. Connaissant plusieurs graphes, on souhaite trouver des base minimums dont l'intersection est la plus grande possible. 

MMCBI : Soient $(G_1, G_2, \dots, G_k)$ des graphes ayant les mêmes n\oe{}uds, trouver un sous-ensemble de cycles $B$ de $\bigcap_{i = 1}^k G_i$ de taille maximum tel que, pour tout $i \in \llbracket 1 ; k \rrbracket$ il existe une base minimum $B_i$ de $G_i$ telle que $B \subseteq B_i$.

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. Nous étudions la capacité de la similarité entre les base minimums des conformations d'une trajectoire à caractériser de telles propriétés. Cette présentation se concentre uniquement sur notre capacité à résoudre le problème MMCBI. 

On peut également noter que MMCBI est un cas particulier du problème d'intersection de matroïdes dans lequel, connaissant $k$ matroïdes avec les mêmes éléments, la question est de trouver un ensemble d'éléments indépendants de taille maximum. Ce problème est polynomial quand $k = 2$, NP-Complet quand $k = 3$ et $\frac{1}{k}$-approximable. 


De précédents travaux ont exploré la complexité paramétrée et l'approximabilité du problème. Ces travaux visent à compléter les résultats existant. En particulier, un point d'attention est mis sur la différence existante entre la complexité de MMCBI et du problème d'intersection de matroïdes. Une question importante est de déterminer si, dans le problème MMCBI, il est possible de profiter de propriétés particulières des graphes en entrée ou de paramètres spécifiques aux graphes, pour mettre en place des algorithmes paramétrés ou d'approximation efficaces. La présentation illustrera quelques éléments de preuves liés à cette question.