PROBLEMA NPC Somma minima della colorazione del vertice

Question

per un grafico G e un vertice legale-colorazione ψ: V (G) → N di G,

Lascia che σψ (g) sia la somma di ψ (V),

e set σ (G):= min σψ (G),

Dove il minimo varia su tutte le colorazioni vertice valide di G.

Dimostrare che {(G, K): Σ (G) ≤ K} ∈ NPC.

Ho pensato di riduzione del sottoinsieme, ma il mio problema è con il minuto e non con la somma, non capisco come fare una riduzione per controllare il minimo. Ho un suggerimento per fare una riduzione da 3-nae-sat ma non capisco come. apprezzerebbe un aiuto.Anche qualche fonte posso leggere su questo problema se sai di qualcosa.

Answer 1

Ridurremmo da 3Col, che è il seguente problema: dato un grafico, è 3-colorable?

Dato un grafico $ g= (v, e) $ , costruiamo un nuovo grafico $ G '$ < / span> su $ v \ time \ {1,2,3 \} $ , i cui bordi sono $$ \ {((i, a), (j, a)) \ metà (I, j) \ in e, a \ in [3] \} \ cup \ {(i, a), (i, b) ) \ metà I \ in V, 1 \ Leq A A parole, prendiamo tre copie di $ G $ e collegare tutte le copie dello stesso vertice.

se $ G $ è 3-colorable Then $ G '$ può essere a 3 colori: Data una classe a 3 colori $ \ chi $ di $ v $ , colore $ (I, a) $ con il colore $ \ chi (i) + a \ bmod 3 $ . La somma dei colori è $ 6 | V | $ .

Viceversa, supponiamo che $ G '$ ha una colorazione $ \ chi' $ la cui somma è al massimo $ 6 | V | $ . Si noti che le tre copie di ogni vertice $ (I, 1), (I, 2), (i, 3) $ devono essere assegnati diversi colori, che somma a Almeno $ 6 $ . Pertanto $ \ sigma \ chi '\ geq 6 | v | $ per qualsiasi colorazione $ \ chi '$ e $ \ sigma \ chi'= 6 | v | $ IFF $ \ Chi ' $ è un 3 colori. Considerando una delle copie di $ G $ , vediamo che $ G $ è 3-colorable. < / P >.