作业 12

算法描述：设 \(G = (V, E)\) 为最小顶点覆盖（MVC）问题的一个实例。构造一个最小集合覆盖（MSC）问题的实例，其中全集 \(U = E\)，且对每个 \(u \in V\)，集合 \(S_u\) 包含所有与 \(u\) 关联的边。

设 \(C_\mathcal{S} = \{S_{u_1}, S_{u_2}, \ldots, S_{u_k}\}\) 为一个集合覆盖，其中 \(k = |C_\mathcal{S}|\)。则我们对应的顶点覆盖为 \(C_V = \{u_1, u_2, \ldots, u_k\}\)。

正确性证明：为说明 \(C_V\) 是一个顶点覆盖，任取 \((u, v) \in E\)。由于 \((u, v) \in U\)，存在某个集合 \(S_{u_i}\) 包含 \((u, v)\)，因此 \(u_i\) 等于 \(u\) 或 \(v\)，从而 \((u, v)\) 在顶点覆盖中被覆盖。于是图 \(G\) 中的每个顶点覆盖都对应 \((U, \mathcal{S})\) 中的一个集合覆盖。

反之，任取一个顶点覆盖 \(u_1, \ldots, u_k\)。为说明 \(S_{u_1}, \ldots, S_{u_k}\) 是一个集合覆盖，任取 \((u, v) \in E\)。由顶点覆盖的定义，存在某个 \(i\) 使得 \(u = u_i\) 或 \(v = u_i\)。因此 \((u, v) \in S_{u_i}\)，故 \(S_{u_1}, \ldots, S_{u_k}\) 是一个集合覆盖。于是 \((U, \mathcal{S})\) 中的每个集合覆盖都对应图 \(G\) 中的一个顶点覆盖。

由于每个顶点覆盖都有对应的集合覆盖（反之亦然），且最小化集合覆盖等价于最小化对应的顶点覆盖，该规约成立。

(a) 添加边 \((x_i, \neg x_i)\)、\((x_i, v_\text{BASE})\) 和 \((\neg x_i, v_\text{BASE})\)。由于 \(x_i\) 和 \(\neg x_i\) 都与 \(v_\text{BASE}\) 相邻，它们必须被分配与 \(v_\text{BASE}\) 不同的颜色，即它们都被分配 \(v_\text{TRUE}\) 或 \(v_\text{FALSE}\) 的颜色之一。由于在 \(x_i\) 与 \(\neg x_i\) 之间添加了边，它们不能被分配相同颜色，即一个被分配与 \(v_\text{TRUE}\) 相同的颜色，另一个被分配与 \(v_\text{FALSE}\) 相同的颜色。

(b) 等价地证明：若右侧所有灰色顶点都被分配红色，则左侧的灰色顶点也必须被分配红色。考虑右侧的三角形。由于所有灰色顶点都被分配红色，右侧的两个顶点必须被分配绿色和蓝色，因此在任何合法着色中，该三角形左侧的顶点必须被分配红色。对左侧的三角形重复此逻辑，可得左侧的灰色顶点在任何合法着色中必须被分配红色。

(c) 给定一个 3-SAT 实例，创建问题描述中的三个特殊顶点及边。如 (a) 部分，对每个变量 \(x_i\) 创建顶点 \(x_i\) 和 \(\neg x_i\)，并添加 (a) 答案中给出的边。对子句 \(j\)，添加一个顶点 \(C_j\) 以及边 \((C_j, v_\text{FALSE})\)、\((C_j, v_\text{BASE})\)。最后，对子句 \(j\) 添加顶点与边以构造一个 gadget，其中 gadget 右侧的三个灰色顶点为该子句中三个文字（literal）对应的顶点，左侧的灰色顶点为顶点 \(C_j\)（gadget 中所有白色顶点仅用于该子句的 gadget）。

若存在满足的 3-SAT 赋值，则按如下方式得到图的一个合法 3-着色：令 \(v_\text{FALSE}\) 为红色，\(v_\text{TRUE}\) 为绿色，\(v_\text{BASE}\) 为蓝色；若 \(x_i\) 为真则 \(x_i\) 为绿色，若 \(x_i\) 为假则 \(x_i\) 为红色（\(\neg x_i\) 反之）。令每个 \(C_j\) 为绿色。最后，取任意一个 gadget。由于该 3-SAT 赋值是满足的，在每个 gadget 中右侧至少有一个灰色顶点被分配绿色，因此由问题描述中的观察 (ii)，该 gadget 可被着色。

若存在合法 3-着色，则存在满足的 3-SAT 赋值。由对称性，可假设 \(v_\text{FALSE}\) 为红色，\(v_\text{TRUE}\) 为绿色，\(v_\text{BASE}\) 为蓝色。于是，对每个文字，若 \(x_i\) 为绿色，则该文字在满足赋值中为真。由 (a) 部分，\(x_i\) 和 \(\neg x_i\) 中恰好有一个为绿色，因此这产生一个合法赋值。由观察 (i)，我们还知道每个节点 \(C_j\) 必须为绿色。所有文字节点为红色或绿色，因此由 (b) 部分，这意味着对每个子句，该子句 gadget 中有一个灰色文字节点为绿色，即该子句在 3-SAT 赋值中将被满足。

(a) 对每个顶点 \(i\) 创建一个变量，对每条边 \((i, j)\) 创建一个子句 \(x_i \text{ XOR } x_j\)。取 \(c = r\)。

对任意赋值，考虑割 \(S\) 包含所有满足 \(x_i\) 在此赋值中为真的顶点 \(i\)。对每条穿过该割的边 \((i, j)\)，其对应的子句为真，因为 \(x_i\) 和 \(x_j\) 中恰好有一个为真。对每条不穿过该割的边，其对应的子句为假，因为 \(x_i\) 和 \(x_j\) 要么都为真要么都为假。这证明了规约的正确性。

(b) 该规约是添加一个新变量 \(y\)，并将 \(y\) 添加到 Max 3-XOR 实例的每个子句中，并取相同的 \(r\) 值，从而得到一个 Max 4-XOR 实例。

给定一个在 Max 3-XOR 实例中满足 \(r\) 个子句的赋值，将 \(y\) 设为假后，同样的赋值在 Max 4-XOR 实例中也满足 \(r\) 个子句。给定一个在 Max 4-XOR 实例中满足 \(r\) 个子句的赋值，若 \(y\) 为假，则去掉 \(y\) 后的赋值在 Max 3-XOR 实例中满足 \(r\) 个子句。否则 \(y\) 为真，去掉 \(y\) 并对所有其他变量取反后的赋值在 Max 3-XOR 实例中满足 \(r\) 个子句。

为说明这一点，考虑在 Max 4-XOR 中为真的任意子句。删除 \(y\) 会使其从有奇数个真变量变为有偶数个。然后，由于 3 是奇数，对所有变量取反会使其回到有奇数个真变量。类似地，在 Max 4-XOR 实例中为假的任意子句有偶数个真变量。删除 \(y\) 导致其有奇数个真变量，然后对所有其他变量取反使其回到偶数。

证明最小支配集属于 NP。

给定一个候选解，我们可以通过遍历不在解子集 \(D\) 中的顶点并检查它是否有邻居在 \(D\) 中来验证其是否为解。这最多需要 \(O(E)\) 时间，因为你最多检查每条边两次。还应检查 \(D\) 中的顶点数是否小于 \(k\)，这最多需要 \(O(V)\) 时间（因为 \(k\) 应小于 \(E\)）。因此，我们可以在 \(O(E)\) 的多项式时间内验证。

证明最小支配集是 NP-Hard。

从顶点覆盖到支配集的规约

最小顶点覆盖是找一个大小 \(\leq k\) 的顶点覆盖（顶点的子集），其中所有边有一个端点在顶点覆盖中。

设 \(G(V, E)\) 为顶点覆盖的一个实例，我们试图找一个大小 \(\leq k\) 的顶点覆盖。对每条边 \((u, v)\)，我们添加一个新顶点 \(c\) 以及两条边 \((c, u)\) 和 \((c, v)\)。我们将相同的 \(k\) 传给支配集。这是一个多项式规约，因为我们添加了 \(|E|\) 个顶点和 \(2|E|\) 条边。

规约的正确性证明

1. 若最小顶点覆盖有解，则其对应的最小支配集有解。

设我们有一个大小为 \(k\) 的最小顶点覆盖。由顶点覆盖的定义，每条边有一个或两个端点在顶点覆盖中。因此，若称该顶点覆盖为一个支配集，则每个原始顶点要么在支配集中，要么与之相邻。现在需要确认为每条边添加的顶点是否被覆盖。由于每条边必须有一个或两个端点在顶点覆盖中，添加的顶点必须至少与顶点覆盖中的一个顶点相邻。因此，顶点覆盖直接映射到变换后问题的一个支配集。

1. 若变换后格式的最小支配集有解，则其对应的最小顶点覆盖有解。

设我们有一个大小为 \(k\) 的变换格式的最小支配集。支配集中的顶点要么来自原始顶点，要么来自我们添加的顶点。若它们不来自变换中添加的顶点，则由前一方向的逻辑，支配集直接对应于顶点覆盖。若有些顶点来自变换，则我们可以将该顶点替换为其对应边的任一端点，而不改变支配集的大小。因此，我们可以得到一个仅使用原始问题顶点的、大小为 \(k\) 的支配集，它将直接对应于原始问题中大小为 \(k\) 的最小顶点覆盖。

替代证明：从集合覆盖到支配集的规约

最小集合覆盖是找一个大小 \(\leq k\) 的集合覆盖（所有集合的子集），其中所有元素被集合覆盖中的至少一个集合覆盖。

设 \((S, U)\) 为集合覆盖的一个实例，其中 \(U\) 表示所有不同元素的集合，\(S\) 是 \(U\) 的子集 \(S_i\) 的集合。如下构造图 \(G = (V, E)\)。对 \(U\) 中的每个元素 \(u\) 构造一个顶点，称为"元素顶点"。对每个可能的 \(S_i\) 构造一个顶点，称为"集合顶点"。将每个顶点 \(S_i\) 连接到所有在 \(S_i\) 中的 \(u\)。注意，若此时对图运行支配集，可以用任意合法集合覆盖覆盖所有元素顶点，但必须选取每个集合顶点才能确保所有集合顶点被覆盖。为修正此问题，将每个集合顶点与其他所有集合顶点连接，形成一个团（clique）。这确保通过选取一个集合顶点即可覆盖所有集合顶点。这样我们实际上只需关注覆盖元素顶点。

规约的正确性证明

1. 若最小集合覆盖有解，则其对应的最小支配集有解。

设我们有一个大小为 \(k\) 的最小集合覆盖。这将对应于一个大小为 \(k\) 的支配集。对最小集合覆盖中的每个集合，选取对应的集合顶点。由图的构造及集合覆盖的定义直接可知，所有集合顶点和元素顶点都被覆盖。

1. 若变换后格式的最小支配集有解，则其对应的最小集合覆盖有解。

设我们有一个大小为 \(k\) 的支配集 \(D\)。我们可以找到一个大小 \(\leq k\) 的集合覆盖。为此，我们构造一个新的仅包含集合顶点的支配集 \(D'\)。将 \(D\) 中的每个集合顶点加入 \(D'\)。对支配集中每个为元素顶点的顶点，任选一个相邻的集合并加入 \(D'\)。观察到 \(|D'| \leq |D|\)。因此，若 \(G\) 中存在大小 \(\leq k\) 的支配集，则必存在大小 \(\leq k\) 的集合覆盖。

由于该问题属于 NP 且是 NP-Hard 的，它必为 NP-Complete。

我们使用一个 \(O(2^{n/2} m)\) 时间复杂度的从 3-SAT 到正交向量的规约。将变量分成两个大小为 \(n/2\) 的组 \(V_1\)、\(V_2\)。对每组，枚举这些变量的所有 \(2^{n/2}\) 种可能赋值。对 \(V_1\) 中变量的每个赋值 \(x\)，令 \(v_x\) 为一个向量，其中第 \(i\) 个分量在该赋值中 \(V_1\) 的变量满足了第 \(i\) 个子句时为 0，否则为 1。我们忽略子句中属于 \(V_2\) 的变量。例如，若子句 \(i\) 仅包含 \(V_2\) 中的变量，则对所有 \(x\) 有 \(v_x(i) = 1\)。令 \(A\) 为以此方式产生的 \(2^{n/2}\) 个向量。

类似地构造 \(B\)，包含 \(2^{n/2}\) 个向量，但使用 \(V_2\) 而非 \(V_1\)。我们断言：3-SAT 实例是可满足的，当且仅当在 \(A \times B\) 中存在一对正交向量。基于此断言，我们可以在 \(O(2^{n/2} m)\) 时间内构造正交向量实例，然后在 \(O((2^{n/2})^c m) = O(2^{c n/2} m)\) 时间内求解该实例，从而求解 3-SAT。

设 3-SAT 存在一个满足赋值。令 \(x_1\) 为 \(V_1\) 中变量的赋值，\(x_2\) 为 \(V_2\) 中变量的赋值。令 \(v_1\)、\(v_2\) 为 \(A\)、\(B\) 中对应于 \(x_1\)、\(x_2\) 的向量。由于每个子句都被满足，对每个 \(i\)，\(v_1(i)\) 和 \(v_2(i)\) 中必有一个为 0，因此 \(v_1 \cdot v_2 = 0\)。故在正交向量实例中也存在一对正交向量。

设在正交向量实例中存在一对正交向量 \(v_1\)、\(v_2\)。则对每个 \(i\)，\(v_1(i)\) 或 \(v_2(i)\) 为 0。相应地，对 \(V_1\)、\(V_2\) 中变量的对应赋值，这些赋值的组合必须满足每个子句。因此，这些赋值的组合是 3-SAT 的一个满足赋值。

注：人们普遍认为 SAT 不存在 \(O(2^{0.999n} m)\) 时间复杂度的算法——这被称为强指数时间假说（Strong Exponential Time Hypothesis，SETH）。因此人们也普遍认为正交向量不存在 \(O(n^{1.99} m)\) 时间复杂度的算法，因为否则 SETH 将被违反。事实上，我们可以将正交向量规约到字符串问题如编辑距离（edit distance）和最长公共子序列（longest common subsequence），因此如果我们相信 SETH，我们也相信那些问题不存在 \(O(n^{1.99})\) 时间复杂度的算法。研究这些问题之间多项式时间规约的领域被称为精细复杂度（fine-grained complexity），正交向量是该领域的核心问题之一。