Lucas est ATER à l’Université de Strasbourg.
Titre : Diviser les sommets d’un graphe pour en faire une union de 2-clubs.
Résumé : Un problème classique consiste à supprimer des sommets d’un graphe jusqu’à ce qu’il devienne une union de cliques. Minimiser le nombre de suppressions est alors NP-difficile. D’autres variantes ont été étudiées : en changeant les opérations (ajout ou suppression d’arêtes), en cherchant à ce que le graphe vérifie certaines propriétés. Notre sujet de recherche à été d’étudier l’opération de division de sommets (ou vertex splitting) consistant à remplacer un sommet par deux sommets de sorte que chaque voisin du sommet original soit adjacent à au moins un des deux sommets. Nous avons étudié la complexité pour minimiser le nombre de splits pour faire du graphe une union de 2-clubs. On verra que ce problème est NP-difficile, FPT et
APX-hard.
Site web : https://lucas-isenmann.github.io/