DEMI CLIQUE - NP complet Problème

Question

Permettez-moi de commencer en notant Ceci est un problème de travail, s'il vous plaît fournir des conseils et des observations que connexes, RÉPONSES NON DIRECT Veuillez . Cela dit, voici le problème que je suis à la recherche:

  

Soit DEMI-CLIQUE = {$ \ langle G \ rangle $ | $ G $ est un graphe non orienté ayant une complète   sous-graphe d'au moins n / 2 $ nœuds de $, où n est le nombre de noeuds dans $ G $   }. Montrer que DEMI-CLIQUE est NP-complet.

En outre, je sais ce qui suit:

• En ce qui concerne ce problème, un clique , est défini comme un sous-graphe non orienté du graphique d'entrée, dans lequel tous les deux noeuds sont reliés par une arête. $ k $ -clique est une clique qui contient $ k nœuds de $.
• Selon notre manuel, Michael Sipser " Introduction à la théorie de calcul ", page 268, que le problème CLIQUE = {$ \ langle G, k \ rangle $ | $ G $ est un graphe non orienté avec un -clique $ k $} est dans NP
• En outre, selon la même source (sur pg 283) note que CLIQUE est NP-Complpete (donc aussi évidemment NP).

Je pense que je le noyau d'une réponse ici, mais je pourrais utiliser une indication de ce qui ne va pas avec elle ou des points connexes qui pourraient être pertinents pour une réponse . Telle est l'idée générale que j'ai jusqu'à présent,

  

Ok, je voudrais tout d'abord noter qu'un certificat serait tout simplement un demi-QLIQUE de texte $ \ {size} \ geq n / 2 $. Maintenant, il semble que ce que je besoin de faire est de créer un vérificateur qui est une réduction du temps de polynomiale CLIQUE (que nous savons est NP-complet) à DEMI-CLIQUE. Mon idée serait que cela se ferait en créant une machine de Turing qui fonctionne la machine turation vérificateur dans le livre pour CLIQUE avec la contrainte supplémentaire pour la demi-CLIQUE.

Cela semble me corriger, mais je ne me suis pas vraiment confiance encore dans ce sujet. Encore une fois, je voudrais rappeler à tout le monde Ceci est un problème de DEVOIRS donc s'il vous plaît essayer d'éviter de répondre à la question. Toute orientation qui est loin de ce serait la bienvenue!

Answer 1

A en juger par votre description et les commentaires, vous pourriez être aidé le meilleur par une description exacte de la façon dont les réductions peuvent être utilisées pour prouver NP-complet:

A problème est NP-complet ssi il est dans NP et il est NP-dur. Cela signifie que toute preuve de NP-complet comporte deux parties: une preuve que les mensonges de problème dans NP et une preuve qu'il est NP-dur

.

Pour la première partie, vous devez montrer que OUI-instances peuvent être vérifiées en temps polynomial en utilisant un certain certificat approprié. Vous pouvez montrer le problème peut être résolu en temps polynomial par une machine de Turing non-déterministe, mais cela ne se fait pas souvent que les erreurs sont faciles à faire.

Dans votre cas, cela revient à prouver que pour chaque graphique avec un n / 2 $ -clique $, vous pouvez trouver une preuve qu'il existe bien une telle clique, de telle sorte que, armé d'une telle preuve, vous pouvez vérifier en temps polynomial qu'il ya effectivement clique un.

Pour la deuxième partie, vous devez montrer que le problème est NP-dur. Ceci est dans presque tous les cas montrés en prouvant que votre problème est au moins aussi dur que d'autres problèmes NP-dur. Si DEMI-CLIQUE est au moins aussi dur que CLIQUE, il doit aussi être NP-dur.

Vous faites cela en prouvant une réduction FROM CLIQUE, à DEMI-CLIQUE. Vous réduisez 'le problème, ce qui rend plus « facile ». Vous dites « Résolution des CLIQUE est difficile, mais je ne prouvé que vous avez seulement besoin de résoudre DEMI-CLIQUE pour résoudre CLIQUE ». (Beaucoup de gens, même des experts, disent parfois ce dans le mauvais sens:))

Il existe différents types de réductions: la réduction qui est le plus couramment utilisé est celui où vous associez des cas dans la présente affaire CLIQUE aux instances de demi-CLIQUE dont la taille est au plus polynomiale plus, en temps polynomial. Cela signifie que si nous pouvons résoudre DEMI-CLIQUE, nous pouvons également résoudre CLIQUE en enchaînant l'algorithme et la réduction.

En d'autres termes, nous devons montrer que nous pouvons résoudre CLIQUE si nous pouvons résoudre DEMI-CLIQUE. Nous faisons cela en montrant que pour chaque instance pour CLIQUE, nous pouvons concevoir une instance de demi-CLIQUE telle que l'instance de CLIQUE est un « oui » par exemple ssi l'instance de demi-CLIQUE est une instance « oui ».

La preuve commence donc comme ceci: étant donné un graphe $ G = (V, E) $, je peux créer un graphe $ H = (V 'E') $ tel que $ G $ contient un k $ - clique ssi $ H $ contient un -clique de $ n $ / 2. Je vais laisser cette partie à vous (ce qui est la partie qui exige de la créativité, la partie qui est sur le problème spécifique à la main).

Answer 2

Vous semblez un peu perdu. Vous voulez montrer que la demi-CLIQUE $ \ ge $ CLIQUE, ce qui signifie que vous êtes à la recherche d'un algorithme poly-temps qui prend des instances CLIQUE comme les instances d'entrée et de sorties DEMI-CLIQUE avec la propriété que « oui » entrées carte à " oui "es et « pas » entrées carte à « aucun » s.

Donc, en gros, la tâche est de prendre un graphique $ G $ et $ et sortie numéro de k $ un nouveau graphique $ H $ (et aucun numéro) de sorte que $ H $ a une clique sur au moins la moitié de sa sommets chaque fois que $ G $ a une clique de taille $ k $.

Le spoiler ci-dessous contient une indication sur la façon d'effectuer cette réduction:

  

Essayez de faire $ H $ en attachant (en quelque sorte) une clique de taille appropriée à $ G $, plus un certain nombre de sommets non relié à quoi que ce soit.

Answer 3

Vous pouvez réduire le problème de la couverture de sommet. Si le graphique du complément du graphique donné a une couverture de sommet moins de noeuds n / 2, alors ce graphique aura une clique de plus de n / 2 nœuds qui est ce sera une clique de moitié. état juste qu'il est difficile de résoudre le problème Vertex est donc ce.