Ce mémoire d’Habilitation à Diriger des Recherches présente un parcours scientifique construit par allers-retours entre théorie des graphes, expérimentation algorithmique et applications interdisciplinaires. Le fil directeur en est l’étude de structures discrètes ou de données complexes lorsque l’optimalité, la robustesse ou la capacité de généralisation dépendent de contraintes cachées, de configurations critiques ou de signaux difficiles à isoler.
La première partie rassemble des contributions en théorie des graphes autour de problèmes classiques d’optimisation combinatoire. Elle étudie l’effet de contraintes d’inclusion, d’exclusion et d’incompatibilité sur des problèmes de couverture, de domination et d’arbre de Steiner, puis introduit une analyse structurelle des solutions optimales à travers les notions de sommets persistants, substituables ou absents des ensembles dominants minimums. Ces travaux conduisent à des résultats de complexité, à des caractérisations dans certaines classes de graphes et à la résolution de questions ouvertes. Ils sont prolongés par l’étude d’un paramètre de qualité locale des bipartitions, relié aux matching-cuts et au produit cartésien de graphes.
La deuxième partie développe une approche expérimentale centrée sur l’apprentissage automatique en contexte de données rares, bruitées et de forte dimension relative. Elle conduit à la conception de TiDE, une métaheuristique fondée sur l’évolution différentielle, adaptée à la sélection de variables par une initialisation informée, une pression de sélection pilotée par la diversité et un croisement adaptatif. Cette approche est ensuite transposée à l’invalidation automatique de conjectures en théorie des graphes, ouvrant une perspective méthodologique vers l’assistance algorithmique à la découverte mathématique.
La troisième partie présente deux domaines d’application. Le projet FinElink mobilise apprentissage de variété, recommandation et analyse de réseaux pour aider à identifier des dispositifs de financement de l’innovation et à structurer des consortiums pertinents. Les travaux sur la Sclérose Latérale Amyotrophique exploitent sélection de variables, modèles interprétables et validation externe pour prédire la survie à un an et l’évolution fonctionnelle des patients. L’ensemble du mémoire articule ainsi preuve, expérimentation et transfert applicatif, avec un projet de recherche orienté vers la génération automatique d’instances, la découverte algorithmique et l’intégration raisonnée des grands modèles de langage dans le processus scientifique.
Mots-clés : théorie des graphes, optimisation combinatoire, domination, persistance, métaheuristiques, sélection de variables, apprentissage automatique, données médicales, SLA, FinElink, génération de contre-exemples.