动机
图着色归约必须把逻辑约束转化为局部的边约束。仅仅说一个构件“表示一个子句”,并没有回答真正重要的问题:该构件终端上的哪些颜色分配可以扩张为一个合法着色?
我们构造一个小型子句构件,并逐一检验它所有的终端情形。再配合一个为三种颜色命名的三角形,以及为每个变量设置的一对顶点,就得到一个从 3-SAT 到图三着色问题的完整多项式时间归约。
定义
定义 4.3.1
(合法三着色)
图的一个合法三着色(proper three-coloring)是给无向图的每个顶点指定三种颜色之一,使得相邻顶点的颜色不同。该判定问题询问这样的着色是否存在。
从每个子句恰有三个文字出现的 3-CNF 公式出发。允许文字重复,因此只含一个或两个文字的子句可以通过重复已有文字补足,而不改变其真值。空子句是立即不可满足的情形,可以映射到一个固定的不可三着色的图。3-SAT 的 NP 完全性是引入的起始定理。
定义 4.3.2
(调色板三角形与变量对)
建立一个由调色板顶点 构成的三角形。在任何合法三着色中,这三个顶点获得三种互不相同的颜色。我们也用这些名字来称呼它们的颜色;对三种实际颜色重新命名不影响可着色性。对每个变量 ,建立顶点 与 ,把它们彼此相连,并把两者都与 相连。于是它们必须按某种次序分别获得 与 ,从而编码一个真值及其相反值。
定义 4.3.3
(子句构件)
对于文字顶点为 的子句,添加四个全新的内部顶点 以及九条边
每个子句都有自己的内部顶点。三个终端名称 可以指代重复的或互补的文字顶点;证明只使用它们实际获得的颜色。
定理
定理 4.3.4
(子句构件性质)
设 各自被染成 或 ,则四个内部顶点可以被合法着色,当且仅当 中至少有一个的颜色为 。
定理 4.3.5
(三着色是 NP 完全的)
该构造把公式映射为一个图,此图可三着色恰好当公式可满足。因此图三着色问题是 NP 完全的。
证明:全假的子句无法着色
证明
(全假模式迫使矛盾)
设 。由于 与 相邻且 ,故 必须取颜色 。同理 。顶点 与 相邻且 ,所以 。顶点 与 、 以及 相邻,因此没有可用的颜色。该构件无法被合法着色。
由于三角形的存在,三种调色板颜色互不相同。该论证并不依赖它们的外部名称:在任一合法着色之后,把调色板顶点 的颜色称为假色,对 与 同理。
概念视角结构
着色等价于映到三角形的同态
图的合法三着色,等价于从顶点到三角形三个顶点的保持邻接的映射:相邻顶点必须映到不同、因而相邻的三角形顶点。这样看,构造中的调色板三角形就是目标图的一个副本,把一个顶点连到某一个调色板顶点,只是禁止它取那个像;连到其中两个,才把它的像钉在第三个上。子句构件随后对它三个终端的像施加一个关系,而定理说明这个关系是“至少有一个为 ”。
证明:其余每种终端分配都可以扩张
证明
(其余七种模式的明确扩张)
下表对每个至少含一个真终端的分配给出一个合法的内部着色。各列依次列出 的颜色。
| F | F | T | G | G | T | F |
| F | T | F | G | F | G | T |
| F | T | T | G | F | T | F |
| T | F | F | F | G | T | G |
| T | F | T | F | G | T | G |
| T | T | F | F | F | T | G |
| T | T | T | F | F | T | G |
每一行都可以对照九条边来检验: 与 都不同于 ; 不同于 ; 分别不同于 ;并且三条内部边 的两个端点颜色不同。结合全假子句的论证,此表即证明了构件性质。
证明透视
构件的每条边用在哪里
在全假模式中,各条边构成一条强制链。当 时,边 与 使 只能取颜色 ;同理 与 使 。然后 与 迫使 ,最后 经 、 与 同时遇上三种颜色。九条边各有分工: 把构件接到调色板, 接上终端, 连接内部顶点。
不显而易见的是,单个为真的终端恰好在它所接触的顶点处截断这条链: 为真使 可取 , 为真使 可取 , 为真使 可取 。表格检验每一种截断都留下一个一致的着色。没有表格,论证只说明了假子句被拒绝,却没有说明被满足的子句会被接受。
证明:公式与图的等价性
证明
(可满足性与三着色性相符)
给定一个满足赋值,先用三种不同的颜色为调色板三角形着色。对每个变量,按赋值把其正文字顶点染成 或 ,并把负文字顶点染成相反的颜色。变量边是合法的。每个子句至少有一个真终端,故选取表中对应的行为它的四个全新内部顶点着色。由于不同的子句构件只共享文字顶点和调色板顶点,这些选择互不冲突。整个图因而被合法地三着色。
反之,设该图有一个合法三着色。调色板三角形使用三种不同的颜色。每个变量对中的两个顶点彼此相邻且都与 相邻,所以其中一个文字顶点的颜色为 ,另一个为 。令变量为真,当且仅当其正顶点被染成 。每个子句构件都有合法的内部着色,因此由构件性质,其终端不可能全为 。于是在所得赋值下,每个子句中至少有一个文字为真。故公式可满足。
对于 个变量与 个子句,该图有 个顶点,在去除重复边之前至多有 条边。它可以由显式给出的公式在多项式时间内构造出来。对于给定的三着色,只需检查每个顶点的颜色并比较每条边的两个端点,即可验证,所以三着色属于 NP。从 3-SAT 出发的归约证明了 NP 困难性,从而完成 NP 完全性的论证。
例题详解
例题 4.3.6
(一个真终端)
对终端颜色 ,表中给出 。特别地, 不同于 、 与 ,所以它的三条关联约束都得到满足。
例题 4.3.7
(所有终端皆假)
对 ,被迫的颜色为 与 。顶点 与三种调色板颜色的顶点都相邻,无法着色。这正是该构件必须拒绝的逻辑情形。
例题 4.3.8
(重复的文字)
单位子句 可以写成 。若 ,则它的三个终端全为假,构件不可能着色。若 ,则行 给出合法的扩张。把同一个文字顶点用于三个终端角色并不改变论证。
例题 4.3.9
(变量及其否定)
文字顶点 与 都与 相邻,所以两者都不能使用颜色 。它们之间的边迫使其中一个使用 ,另一个使用 。正是这一图约束使得提取出的真值赋值保持一致。
常见错误
反例模式
缺少边 CD 的构件会接受假子句
声称:边 是多余的,构件只用八条边便可。用模式 来检验。强制的颜色仍然是 (由 得出)以及 (由 与 得出)。 与 及 相邻,所以去掉 之后 是允许的,即使 也一样。其余每条边都合法,所以三个终端皆假的子句也可以着色。为不可满足的公式 构造的图便会是三可着色的,因为终端全是那个假文字顶点的子句不再被拒绝。正是边 使全假模式失败。
常见错误
(预先固定实际的颜色名称)
这个归约并不预先指定固定的实际颜色名称。三角形强制三种不同的颜色;在选定一个着色之后,才以调色板顶点为这三种颜色命名。把三种颜色整体置换,得到另一个合法着色,而相对于调色板,所编码的真值赋值并无改变。
常见错误
(把困难性与属于 NP 当作同一项声称)
NP 困难性与属于 NP 是两项独立的声称。图的构造把困难性由 3-SAT 传过来;在多项式时间内检查一个给定的着色,则确立属于 NP。单凭其中一项都不是完整的 NP 完全性证明。
高效地阅读构件表
这张表不应被当作七个互不相关的猜测。若 ,则最后四行都使用 、 与 ;例外是 的两行使用 ,因为 与 相邻。在每个列出的行中,终端边与内部边是分别检验的。这种组织方式使人更容易看出,即使某些终端角色指代同一个文字顶点,这些见证依然有效。
例如,对 ,取 。终端边是合法的:、,并且 。调色板边是合法的,因为 且 。最后有 、 与 。检验完这九条边之后,不再有任何隐藏的约束。
见证表之所以能证明可扩张,是因为它覆盖了除 以外的全部七种真值模式。并不需要为每种模式列出所有可能的内部着色。反过来,证明全假模式失败本身并不能证明所有满足的模式都可扩张;归约同时用到这两个半部分。
一个完整的小公式
考虑 。把单位子句补足为 与 。变量构件迫使两个文字顶点中恰有一个的颜色为 。于是三次连接到该假文字上的子句构件,其终端模式为 ,无法着色。因此所构造的图不可三着色,与该公式不可满足相吻合。
对于公式 ,取 且 。给每个相反的文字顶点赋予相反的真值颜色。该子句的终端模式为 ,表中给出一个合法的内部着色。这样,从满足赋值就构造出了图着色的见证,而无需在所有图着色中搜索。
验证规模与证书
调色板贡献三个顶点与三条边。每个变量贡献两个顶点与三条边:一条变量对之间的边,以及每个文字顶点各向 连的一条边。每个子句贡献四个全新顶点与九条列出的边。即使一个子句重复某个文字,这仍然只是常数个新增部分;把图表示为简单图时可以去掉重复边,而不改变合法着色性。
着色证书为每个图顶点指定三个标签之一。验证器先检查每个标签是否有效,再扫描边表,若某条边的两个端点颜色相同则拒绝。这所需的时间关于显式列出的顶点与边是多项式的。验证器不需要知道满足赋值,也不必反向执行归约就能检验该证书。
反向的蕴涵对于困难性证明仍然是必不可少的。若不可满足的公式所对应的图竟有合法着色,则着色算法就会对一个为假的源实例回答是。从调色板与变量构件中提取赋值,再对每个子句使用全假不可着色的结论,即排除了这种可能。
子句长度的规范化
含两个文字的子句 可以替换为 ,单位子句 可以替换为 。重复不改变子句的真值。当终端角色重复时,构件表依然有效,因为它只应用于由共享顶点实际诱导出的终端颜色模式。
若公式含有空子句,则它不可满足。一个固定的否实例是四个顶点的完全图:任意两个顶点都相邻,所以需要四种互不相同的颜色。若公式没有子句,则它可满足;所构造的调色板与变量构件只要赋予任意真值即可着色。这些情形使映射在所述的输入约定下是全函数。
加入全能顶点,就能把三着色问题变成 k 着色问题。
通往推广的路径
从三种颜色到 k 种颜色
加入全能顶点,就能把三着色问题变成 k 着色问题。
对 ,在图 中加入 个新顶点,它们彼此相邻,也与 的每个顶点相邻。新顶点使用 种互不相同、且 的顶点不能使用的颜色,所以扩大后的图可 着色,当且仅当 可三着色。因此对每个固定的 , 着色问题都是 NP 完全的。改变的只是调色板;子句构件并未重用。
总结
调色板三角形给出真值颜色,变量对强制相反的真值,而四顶点的子句构件可着色恰好当至少有一个终端为真。把这些构件组合起来,就得到一个多项式时间的 3-SAT 归约以及可验证的着色证书。
练习
快速检查
(为什么变量对中的两个文字顶点都不能取颜色 ?)
留意调色板顶点 。
解答 · 答案
两者都与调色板顶点 相邻,所以合法着色禁止两个端点取颜色 。
快速检查
(在终端颜色为 的子句构件中,为什么必须 ?)
除了终端以外,还有哪些顶点与 、 相邻?
解答 · 答案
两者都与调色板顶点 以及一个颜色为 的终端相邻,只剩下 。
快速检查
(验证表中 那一行里,与 关联的各条边。)
查看表中该行 的颜色。
解答 · 答案
该行 。顶点 与 、 及 都不同,满足它的三条关联边。
快速检查
(为什么所构造图的合法着色能给出满足赋值?)
运用变量对与构件性质。
解答 · 答案
每个变量对使用相反的真值颜色,定义出一个一致的赋值。每个子句构件只有在至少一个终端为 时才可着色,所以每个子句都为真。