Réduction de la couverture de clique à pondération

Question

Clique de pondération

• saisir: Un graphique non dirigé G qui a des bords pondérés et 2 nombres naturels A, B

• question: G a-t-il une clique de taille A avec un poids total de B?

Je veux prouver que c'est du NP-dure (en supposant un clique pondérée $ dans np $)

Alors je devrais prouver

$ Vertexcover leq_p pondéléclique $

Besoin de montrer la transformation: $ (G, k) to (g ', k', d) $

Que je vais faire en utilisant le fait que $ C $ est une couverture de sommet $ G = (v, e) $ chaque fois que $ bar {c} $ est une clique dans $ G = (v, e) $ alors $ overline {c} = | v | - C $

Par conséquent, nous pouvons laisser $ G '= overline {g} $ et $ k '= | v | - k $.

Je dessinerai des exemples de graphiques pour illustrer ceci:

J'ai mis 1 $ G '$ Juste pour montrer qu'ils sont pondérés pour le moment, ils n'ont aucun but car je ne sais pas encore comment les intégrer dans ce problème.

Donc finalement pour prouver cela, je dois montrer

• S'il y a une solution pour $ Vertexcover (g, k) $, alors il doit y avoir une solution à laclique pondérée$ ( overline {g}, | v | - k, d) $ (1)

• S'il y a une solution à laclique pondérée$ ( overline {g}, | v | - k, d) $, alors il doit y avoir une solution à vertexcover$ (G, k) $ (2)

Je sais seulement faire la (2) partie depuis le $ d $ Le numéro pourrait être ignoré.

(2) en utilisant le fait d'en haut $ C $ est une couverture de sommet que nous savons que

Si $ forall u, v in v $, si $ u, v in c $, alors $ (u, v) in e $

Prendre le contrapositif

$ Leftrightarrow forall u, v in v $, si $ (u, v) in overline {e} $, alors $ (u in overline {c} text {ou} v in overline {c}) $. Ce qui indique clairement que $ overline {c} $ est une clique. Cela se fait également en temps polynomial, car nous passons en revue toutes les paires de sommets dans le graphique d'origine qui se fait en temps polynomial.

Maintenant, pour (1) je ne sais pas comment utiliser la couverture du sommet et obtenir un D tel qu'elle est maintenue, si possible.

Toute aide appréciée

Edit: fait le mauvais côté par accident, l'a corrigé