Comme vous le savez, trouver le jeu indépendant maximum est NP. Existe-t-il un algorithme pour savoir si un graphe donné possède un ensemble indépendant d'au moins k sommets? Notez que nous ne voulons pas le trouver. Nous voulons juste savoir si une telle chose existe.Indépendant réglé dans un graphique
mentionnant Wikipedia:
Dans le problème de décision de réglage indépendant, dont l'entrée est un graphe non orienté et un certain nombre k, et la sortie est une valeur booléenne: true si le graphe contient un ensemble indépendant de taille k, et false sinon.
Ce problème est NP-complet. Votre problème pose la même question, juste de manière différente, car un graphe a un ensemble indépendant d'au moins k sommets si et seulement si il a un ensemble indépendant de k sommets. Cela signifie que votre problème est également NP-complet.
Merci! Je ne le savais pas. –
IMO pour être précis, un graphe a un ensemble indépendant d'au moins k sommets s'il a au moins un ensemble indépendant de n sommets avec n plus grand que k. Quoi qu'il en soit, je pense que c'est aussi NP-Complete. – digEmAll