NPC问题最小的顶点着色总和

Question

图G和合法顶点着色ψ：v（g）→n的g，

让Σψ（g）是ψ（v）的总和，

和设置σ（g）：=minσψ（g），

其中最小范围在G的所有有效顶点着色范围内。

证明{（g，k）：σ（g）≤k}∈npc。

我想从子集合中的减少，但我的问题是min而不是总和，我不明白如何减少来检查最小值。 我有一个暗示从3-NAE-SAT减少，但我不明白如何。 会欣赏一些帮助。即使是一些来源，如果你了解某事，我也可以阅读这个问题。

Answer 1

我们将从3Col减少，这是以下问题：给定图形，它是3可色吗？

给定图 $ g=（v，e）$ ，我们构建一个新图 $ g'$ < / span> on $ v \ times \ {1,2,3 \} $ ，其边缘是 $$ \ {（（i，a），（j，a））\ mid（i，j）\在e中，a \在[3] \} \ cup \ {（（i，a），（i，b）中）\ mid i \中的v，1 \ leq a 用文字，我们拍摄了三个 $ g $ ，并连接所有顶点的所有副本。

如果 $ g $ 是3可色，则 $ g'$ 可以是3彩色的：给定3彩色 $ \ chi $ $ v $ ，color $（i，a）$ 使用color $ \ chi（i）+ a \ bmod 3 $ 。颜色的总和是 $ 6 | v | $ 。

相反，假设 $ g'$ 具有着色 $ \ chi' $ 其总和最多 $ 6 | v | $ 。请注意，每个顶点 $（i，1），（i,3）$ 必须分配不同颜色的三个副本，哪个总和至少 $ 6 $ 。因此 $ \ sigma \ chi'\ geq 6 | v | $ 对于任何彩色 $ \ Chi' $ ， $ \ sigma \ chi'= 6 | v | $ iff $ \ chi' $ 是3彩色。考虑到 $ g $ 的一个副本，我们看到 $ g $ 是3可色。< / p>