PROBLEMA NPC Suma mínima de coloración de vértices

Question

para un gráfico G y un vértice legal colorante ψ: V (g) → N de G,

Sea σψ (g) la suma de ψ (V),

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

Donde los rangos mínimos sobre todos los colorantes vértices válidos de G.

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

Pensé en la reducción de la subida de suma, pero mi problema es con el MIN y no con la suma, no entiendo cómo hacer una reducción para verificar el mínimo. Recibí una pista para hacer una reducción de 3-NAE-SAT, pero no entiendo cómo. Agradecería alguna ayuda.Incluso alguna fuente que puedo leer sobre este problema si sabes sobre algo.

Answer 1

Reduciremos de 3COL, que es el siguiente problema: Dado un gráfico, ¿es 3-colorable?

Dado un gráfico $ g= (v, e) $ , construimos un nuevo gráfico $ g '$ < / span> en $ V \ Times \ {1,2,3 \} $ , cuyos bordes son $$ \ {((i, A), (J, A)) \ MID (I, J) \ IN E, A \ IN [3] \ \ \ CUP \ \ {(i, A), (i, b) ) \ media i \ in v, 1 \ leq a En palabras, tomamos tres copias de $ g $ y conecte todas las copias del mismo vértice.

Si $ g $ es 3-colorable, entonces $ g '$ puede ser de 3 colores: Dado una $ \ chi $ de $ v $ , color $ (i, a) $ con el color $ \ chi (i) + a \ bmod 3 $ . La suma de los colores es $ 6 | v | $ .

A la inversa, supongamos que $ g '$ tiene un colorante $ \ chi' $ cuya suma es a la mayoría $ 6 | v | $ . Tenga en cuenta que las tres copias de cada vértice $ (i, 1), (i, 2), (i, 3) $ deben asignarse diferentes colores, que suma a al menos $ 6 $ . Por lo tanto, $ \ sigma \ chi '\ geq 6 | v | $ para cualquier colorante $ \ Chi '$ , y $ \ sigma \ chi'= 6 | v | $ iff $ \ chi ' $ es un color de 3 colores. Teniendo en cuenta una de las copias de $ g $ , vemos que $ g $ es 3-colorable. < / p>