NPC Problema soma mínima da coloração do vértice

Question

Para um gráfico g e uma coloração de vértice legal ψ: v (g) → n de g,

Deixe σψ (g) ser a soma de ψ (v),

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

onde o mínimo varia sobre todas as coloridas vérticas válidas de G.

Prove que {(g, k): Σ (g) ≤ k} ∈ NPC.

Eu pensei em redução da soma do subconjunto, mas meu problema é com o min e não com a soma, não entendo como fazer uma redução para verificar o mínimo. Eu tenho uma dica para fazer uma redução de 3-Nae-sentado, mas eu não entendo como. apreciaria alguma ajuda.Mesmo alguma fonte que posso ler sobre esse problema se você sabe sobre algo.

Answer 1

Vamos reduzir de 3COL, que é o seguinte problema: Dado um gráfico, é 3-colorable?

Dado um gráfico $ g= (v, e) $ , construímos um novo gráfico $ g '$ < / span> em $ v \ vezes {1,2,3 \} $ , cujas bordas são $$ \ {((i, a), (j, a) \ meados (i, j) \ em e, a \ in [3] \} \ copo \ {((i, a), (i, b) ) \ Mid I \ in v, 1 \ leq A Em palavras, tomamos três cópias de $ g $ e conecte todas as cópias do mesmo vértice.

Se $ g $ é 3-colorable, em seguida, $ g '$ pode ser de 3 cor: Dada um 3-colorir $ \ chi $ de $ v $ , cor $ (i, a) $ com a cor $ \ chi (i) + a \ bmod 3 $ . A soma das cores é $ 6 | v | $ .

Por outro lado, suponha que $ g '$ tenha uma coloração $ \ chi' $ cuja soma é No máximo $ 6 | v | $ . Observe que as três cópias de cada vértice $ (I, 1), (i, 2), (i, 3) $ devem ser atribuídas cores diferentes, que somam pelo menos $ 6 $ . Portanto $ \ Sigma \ Chi '\ Geq 6 | v | $ para qualquer coloração $ \ chi '$ , e $ \ sigma \ chi'= 6 | v | $ iFF $ \ chi ' $ é uma coloração de 3. Considerando uma das cópias da $ g $ , vemos que $ g $ é 3-colorable. < / p >.