Diviser les sommets d'un graphe biparti pour en faire une union de graphes bipartis complets
Un problème classique consiste à ajouter ou supprimer des arrêtes d'un graphe biparti jusqu'à ce qu'il devienne une union de graphes bipartis complets. Minimiser le nombre d'opérations est alors NP-difficile. 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 d'opérations à effectuer pour faire du graphe une union de graphes bipartis complets. On verra que ce problème est NP-difficile, FPT et APX-hard et on proposera une heuristique.
