Supprimer les sommets jusqu'à ce qu'il ne reste plus d'arêtes
Étant donné un graphe non orienté G(V,E), trouvez le nombre minimum de sommets à supprimer pour que l'ensemble d'arêtes du graphe devienne vide.
En d'autres termes : si nous supprimons un sommet, nous supprimons ce sommet ainsi que toutes les arêtes connectées à ce sommet. Trouvez le nombre minimum de sommets à supprimer pour qu'il ne reste plus d'arêtes dans G après leur suppression.
Réponses
Il semble que vous ayez trouvé la réponse vous-même, vous décrivez Vertex Cover , qui à bien des égards est très similaire à Independent Set, les deux problèmes sont NP-complets .
La relation avec l'ensemble indépendant est que dans un graphe$G = (V,E)$, un ensemble$S$est une couverture de sommet minimale si et seulement si$V \setminus S$est un ensemble maximal indépendant.
Si vous savez que l'ensemble indépendant est NP-complet, il s'ensuit que Vertex Cover est également NP-complet.
En d'autres termes, vous recherchez également un ensemble indépendant maximum.
Couverture vertex . Étant donné un graphique$G = (V,E)$et un entier$k$, existe-t-il un ensemble$S \subseteq V$de taille au maximum$k$telle que toutes les arêtes de$G$ sont incidents à un sommet dans$S$?
Ensemble indépendant . Étant donné un graphique$G = (V,E)$et un entier$k$, existe-t-il un ensemble$S \subseteq V$de taille au moins$k$tel que le graphe induit $G[S]$n'a pas de bords ?