"Montrer qu'il est NP-complet pour déterminer l'entrée donnée G et k si G a à la fois une clique de taille k et un ensemble indépendant de taille k. , pas 2, la réponse est oui si et seulement si G a ces deux sous-ensembles. "Prove NP-complétude clique + graphe de jeu indépendant
On m'a donné ce problème dans mon cours d'algorithmes et un grand groupe d'étudiants n'a pas pu le comprendre. Voici ce que nous avons jusqu'ici ...
Nous savons que les problèmes de clique et d'ensemble indépendant sont eux-mêmes NP-complets. Nous savons aussi que la vérification de ce problème, étant donné un certain "certificat" est dans NP. Le problème consiste en quelque sorte à réduire le problème ci-dessus (qui contient à la fois des ensembles et des cliques indépendants) à un problème entièrement constitué de cliques ou d'ensembles indépendants (du moins c'est ce que nous pensons devoir faire). Nous ne savons pas comment effectuer cette réduction sans perdre les informations nécessaires pour réduire la réduction à sa forme originale.
Voir aussi [Question à propos de NP-Complétude du problème de l'ensemble indépendant.] (Http://stackoverflow.com/questions/2128839/question-about-np-completeness-of-the-independent-set-problem) – Pops