Prove NP-complétude clique + graphe de jeu indépendant

Question

"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. "

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.

Answer 1

Indice: Réduisez CLIQUE à ce problème en ajoutant des sommets.

Answer 2

Merci à "Moron" et "Rafal Dowgird" pour les conseils! Sur cette base, je pense avoir une solution. S'il vous plaît corrigez-moi si je suis incorrect:

Puisque nous savons déjà que les problèmes de clique et d'ensemble indépendant sont NP-complets, nous pouvons l'utiliser comme base pour prouver notre problème. Appelons notre problème le problème du jeu indépendant de clique combinée (CCIS). Supposons qu'on nous donne un graphe G qui a une clique C de taille k. Nous pouvons réduire ce graphe en un graphe G '(lire: G prime) qui a à la fois une clique C' de taille k 'et un ensemble indépendant I de taille k' en attachant k sommets à chaque sommet en C. Cette réduction se produit dans temps polynomial puisque l'addition des sommets prend le temps O (n * k) (n sommets dans le graphe et k sommets attachés à chaque noeud).

Notez que C = C 'et k = k'. Supposons maintenant qu'on nous donne un graphe G 'qui a une clique C' de taille k 'et un ensemble indépendant I de taille k' qui est déterminé comme vrai. La réduction au problème de clique est triviale puisque nous n'avons pas du tout besoin de modifier le graphique pour trouver seulement une clique.