This Habilitation à Diriger des Recherches (HDR) thesis presents a research trajectory shaped by continuous interactions between graph theory, algorithmic experimentation, and interdisciplinary applications. Its central theme is the study of discrete structures and complex data in settings where optimality, robustness, or generalization depend on hidden constraints, critical configurations, or signals that are difficult to isolate.
The first part gathers contributions in graph theory related to classical problems in combinatorial optimization. It investigates the impact of inclusion, exclusion, and incompatibility constraints on covering, domination, and Steiner tree problems, and develops a structural analysis of optimal solutions through the notions of persistent, substitutable, and absent vertices in minimum dominating sets. These works lead to complexity results, characterizations in specific graph classes, and the resolution of open questions. They are further extended by the study of a local quality parameter for bipartitions, connected to matching-cuts and Cartesian products of graphs.
The second part develops an experimental approach centered on machine learning in contexts involving scarce, noisy, and relatively high-dimensional data. It leads to the design of TiDE, a metaheuristic based on differential evolution and tailored to feature selection through informed initialization, diversity-driven selection pressure, and adaptive crossover. This approach is then transposed to the automatic refutation of conjectures in graph theory, opening a methodological perspective toward algorithm-assisted mathematical discovery.
The third part presents two application domains. The FinElink project combines manifold learning, recommendation methods, and network analysis to support the identification of innovation funding schemes and the construction of relevant consortia. The work on Amyotrophic Lateral Sclerosis relies on feature selection, interpretable models, and external validation to predict one-year survival and patients’ functional decline. Overall, this thesis articulates proof, experimentation, and applied transfer, with a research agenda oriented toward automatic instance generation, algorithmic discovery, and the principled integration of large language models into the scientific process.
Keywords: graph theory, combinatorial optimization, domination, persistence, metaheuristics, feature selection, machine learning, medical data, amyotrophic lateral sclerosis, FinElink, counterexample generation.