NPC Problème somme minimum de colorage de sommet

Question

Pour un graphique G et un sommet juridique-colorant: V (g) → n de g,

Soit σψ (g) la somme de ψ (v),

et set σ (g):= min σψ (g),

où le minimum varie sur tous les colorants de sommet valides de G.

prouver que {(g, k): σ (g) ≤ k} ∈ npc.

J'ai pensé à la réduction du sous-sommet, mais mon problème est avec le min et non avec la somme, je ne comprends pas comment faire une réduction pour vérifier le minimum. J'ai eu une allusion à faire une réduction de 3-Nae-Sat, mais je ne comprends pas comment. apprécierait une certaine aide.Même une source, je peux lire sur ce problème si vous connaissez quelque chose.

Answer 1

Nous réduirons de 3COL, qui est le problème suivant: donné un graphique, est-il 3-colorable?

donné un graphique $ g= (v, e) $ , nous construisons un nouveau graphique $ g '$ < / span> sur $ v \ fois \ {1,2,3 \} $ , dont les bords sont $$ \ {((i, a), (j, a)) \ midi (i, j) \ in e, a \ in [3] \} \ tasse \ {(i, a), (i, b) ) \ mi-i \ in v, 1 \ Leq a En mots, nous prenons trois copies de $ g $ et connectez toutes les copies du même sommet.

si $ g $ est 3-colorable que $ g '$ peut être 3 coulant: Compte tenu d'une $ \ chi $ de $ v $ , couleur $ (i, a) $ avec la couleur $ \ chi (i) + a \ bmod 3 $ . La somme des couleurs est 6 $ | v | $ .

inversement, supposons que $ g '$ a une coloration $ \ chi' $ dont la somme est Au plus 6 $ | V | $ . Notez que les trois copies de chaque sommet $ (i, 1), (i, 2), (i, 3) $ doivent être attribués différentes couleurs, quelle somme à au moins 6 $ . Par conséquent, $ \ SIGMA \ CHI '\ GEQ 6 | V | $ pour tout coloriage $ \ chi '$ , et $ \ sigma \ chi'= 6 | v | $ iff $ \ chi ' $ est un 3-coloration. Compte tenu de l'une des copies de $ g $ , nous voyons que $ g $ est 3-colorable. < / p>