DEMI CLIQUE - Problème NP complet

20

Permettez-moi de commencer par noter qu'il s'agit d'un problème de devoirs, veuillez fournir uniquement des conseils et des observations connexes, AUCUNE RÉPONSE DIRECTE s'il vous plaît . Cela dit, voici le problème que je regarde:

Soit HALF-CLIQUE = { | est un graphe non orienté ayant un sous-graphe complet avec au moins nœuds, où n est le nombre de nœuds dans }. Montrez que HALF-CLIQUE est NP-complete.G n / 2 GGGn/2G

De plus, je sais ce qui suit:

  • En termes de ce problème, une clique est définie comme un sous-graphe non orienté du graphe d'entrée, dans lequel tous les deux nœuds sont connectés par un bord. Une -clique est une clique qui contient nœuds.kk
  • Selon notre manuel, " Introduction à la théorie du calcul " de Michael Sipser , p. 268, que le problème CLIQUE = { | est un graphe non orienté avec une -clique} est en NPG kG,kGk
  • De plus, selon la même source (p. 283) note que CLIQUE est en NP-Complet (donc aussi évidemment en NP).

Je pense avoir le noyau d'une réponse ici, mais je pourrais utiliser une indication de ce qui ne va pas 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 noterais d'abord qu'un certificat serait simplement un HALF-QLIQUE de . Il semble maintenant que ce que je devrais faire est de créer un vérificateur qui est une réduction de temps polynomiale de CLIQUE (que nous connaissons comme NP-Complete) à HALF-CLIQUE. Mon idée serait que cela se fasse en créant une machine de Turing qui exécute le vérificateur de machine de Turing dans le livre pour CLIQUE avec la contrainte supplémentaire pour HALF-CLIQUE.sizen/2

Cela me semble correct, mais je n'ai pas encore vraiment confiance en moi dans ce sujet. Encore une fois, je voudrais rappeler à tout le monde que c'est un PROBLÈME DE DEVOIR, alors essayez d'éviter de répondre à la question. Tout conseil ne répondant pas à ces critères serait le bienvenu!

BrotherJack
la source

Réponses:

15

À en juger par votre description et vos commentaires, vous pourriez être mieux aidé par une description exacte de la façon dont les réductions peuvent être utilisées pour prouver l'exhaustivité de NP:

Un problème est NP-complet s'il est dans NP et NP-difficile. Cela signifie que toute preuve d'exhaustivité de NP comporte deux parties: une preuve que le problème réside dans NP et une preuve qu'il est NP-difficile.

Pour la première partie, vous devez montrer que les instances YES peuvent être vérifiées en temps polynomial en utilisant un certificat approprié. Alternativement, vous pouvez montrer que le problème peut être résolu en temps polynomial par une machine de Turing non déterministe, mais cela n'est généralement pas fait car des erreurs sont facilement commises.

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

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

Pour ce faire, vous prouvez une réduction DE LA CLIQUE À LA DEMI-CLIQUE. Vous «réduisez» le problème, le rendant «plus facile». Vous dites que "Résoudre CLIQUE est difficile, mais j'ai prouvé qu'il suffit de résoudre HALF-CLIQUE pour résoudre CLIQUE". (beaucoup de gens, même des experts, disent parfois cela dans le mauvais sens :))

Il existe différents types de réductions: la réduction la plus couramment utilisée est celle où vous mappez des instances de dans ce cas CLIQUE à des instances de HALF-CLIQUE dont la taille est au plus polynomialement plus grande, en temps polynomial. Cela signifie que si nous pouvons résoudre HALF-CLIQUE, alors 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 HALF-CLIQUE. Nous faisons cela en montrant que pour chaque instance de CLIQUE, nous pouvons concevoir une instance de HALF-CLIQUE de telle sorte que l'instance de CLIQUE soit une instance 'oui' si l'instance de HALF-CLIQUE est une instance 'oui'.

La preuve commence donc comme ceci: étant donné un graphe , je peux créer un graphe H = ( V , E ) tel que G contienne une k -clique ou si H contient une n / 2 -clique. Je vous laisse cette partie (c'est la partie qui nécessite de la créativité, la partie qui concerne le problème spécifique en question).G=(V,E)H=(V,E)GkHn/2

Alex ten Brink
la source
Excellente configuration, je pense que vous avez fait un très bon travail en fournissant juste assez d'informations pour guider sans fournir de réponse et en le faisant de manière éloquente. Je vous remercie.
BrotherJack
1
Quelque chose comme ça devrait être mis dans le wiki wiki de np-complete pour référence future. Cela vous dérangerait?
Raphael
8

GkHHGk

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

HG

Louis
la source
Je ne comprends pas ce que vous dites. Ce que j'ai essayé de faire était de réduire HALF-CLIQUE en CLIQUE en modifiant le varificateur utilisé dans le livre pour prouver que CLIQUE était NP, le faire exécuter sur le graphe d'entrée G, et s'il a trouvé une vérification CLIQUE pour voir si ladite CLIQUE contenait au moins n / 2 nœuds, où n est le nombre de nœuds en G. Un tel vérificateur de HALF-CLIQUE ne montrerait-il pas que le vérificateur de CLIQUE en est une forme réduite (comme dans un sous-problème de résolution de HALF-CLIQUE )?
BrotherJack
Ou dites-vous que je l'ai à l'envers et que je dois prouver que CLIQUE doit être réduite à HALF-CLIQUE? Je ne reçois pas non plus votre spoiler. Existe-t-il un moyen de l'expliquer sans révéler la réponse?
BrotherJack
3
Oui, pour montrer un problème est NP-complet, vous devez (a) montrent qu'il est en NP et (b) réduire un problème NP-dur connu pour elle. Pour se souvenir de la bonne direction pour la réduction, le point est d'utiliser le nouveau problème comme une "boîte noire" pour résoudre efficacement un problème NP-C connu.
Louis
OK, je pense que je comprends maintenant. Merci de votre aide!
BrotherJack
+1 Je pense l'avoir compris. Votre indice a été très instructif une fois que j'ai compris ce que je faisais mal. Merci encore!
BrotherJack
0

Vous pouvez réduire le problème de couverture de sommet. Si le graphe complémentaire du graphe donné a une couverture de sommet inférieure à n / 2 nœuds, alors ce graphe aura une clique de plus de n / 2 nœuds, c'est-à-dire que ce sera une demi-clique. Dites simplement qu'il est difficile de résoudre le problème de la couverture Vertex.

Arnav
la source
1
Comme vous pouvez réduire tout problème NP-complet, ce n'est pas très utile. Des détails sur la réduction sont attendus.
Raphael
n/2