算法：期末复习

本文为SJTU-AI2615算法课程的期末复习，主要复习内容为动态规划、网络流、线性规划、NP完全。

动态规划

DP 的一般方法

• 算法设计方法：

1. 找到子问题（或从递归解法合并重复子问题）
2. 确认在 DAG 中，并找到 DAG 的拓扑序
3. 按照拓扑序，求解子问题并存储

DP 算法设计的关键：子问题定义 & 状态转移方程

• 正确性证明：数学归纳法（按拓扑序）
• 优先级队列优化：掌握类似维护 PLL 的基础方法即可

DP 基础问题示例

斐波那契数列

• 子问题定义：$fib[i]$ 表示斐波那契数列的第 $i$ 项
• 状态转移：$fib[i] = fib[i - 1] + fib[i - 2]$
• 拓扑序：从 $1$ 到 $n$
• 整体算法：

• 时间复杂度：$O(n)$

DAG 最短路径

• 问题描述：
  • 输入：有向无环图 $G$、起点 $s$、边权函数 $w(e)$
  • 输出：$s$ 到所有顶点的最短路径
• 子问题定义：$dist[u]$ 表示 $s$ 到顶点 $u$ 的最短距离
• 状态转移：$dist[u] = \min_{(v, u) \in E} \{dist[v] + w(v, u)\}$
• 拓扑序：即为原图 $G$ 的拓扑序
• 整体算法：

• 时间复杂度：$O(|V| + |E|)$
• 正确性证明：数学归纳法（按拓扑序）

最长递增子序列

• 问题描述：
  • 输入：一个序列 $a_1, a_2, \ldots, a_n$
  • 输出：最长递增子序列长度（LIS）的长度
    • LIS：$a_{i_1} < a_{i_2} < \cdots < a_{i_k}$，其中 $i_1 < i_2 < \cdots < i_k$
• 子问题定义：$lis[i]$ 表示以 $a_i$ 结尾的 LIS 长度
• 状态转移：$lis[i] = \max_{a_j < a_i, j < i} \{lis[j] + 1\}$
• 拓扑序：从 $1$ 到 $n$
• 整体算法：

• 时间复杂度：$O(n^2)$

编辑距离

• 问题描述：
  • 输入：字符串 X 和 Y
  • 输出：将 X 转换为 Y 的最小操作次数（插入、删除、替换）
• 问题转化：找到最好的对齐方式

• 子问题定义：$ED[i, j]$ 表示 X[1..i] 和 Y[1..j] 之间的编辑距离
• 状态转移：考虑 X 和 Y 结尾的一位

$$ED[i, j] = \min \begin{cases} \, ED[i-1, j-1] + 1_{x_i \neq y_j} & \text{替换} \\ \, ED[i, j-1] + 1 & \text{插入} \\ \, ED[i-1, j] + 1 & \text{删除} \end{cases}$$

• 拓扑序：

• 时间复杂度：$O(mn)$

背包问题

• 问题描述：
  • 输入：$n$ 件物品，第 $i$ 件物品代价 $c_i$，价值 $v_i$，背包容量 $W$
  • 输出：选择物品子集，使得总代价不超过 $W$ 且总价值最大
• 子问题定义：$f[i, w]$ 表示考虑前 $i$ 件物品，使用 $w$ 容量时的最大价值
• 状态转移：考虑是否选择第 $i$ 件物品

$$f[i, w] = \max \{ f[i − 1, w], f[i − 1, w − c_i] + v_i \}$$

• 拓扑序：

• 时间复杂度：$O(nW)$，但不是多项式

优先级队列优化示例

连续 k 个数中的最大值

• 问题描述：
  • 输入：数组 $a_1, a_2, \ldots, a_n$ 和 整数 $k$
  • 输出：每个长度为 $k$ 的连续子数组中的最大值

• 思路：维护一个单调递减队列 Potential Largest List（PLL），保存潜在最大值
  • 队列性质：队首元素是当前窗口最大值，队列中元素按索引递增且值递减
  • 更新步骤：
    • ​移除过期元素：若队首元素索引超出窗口左边界，弹出队首
    • ​维护单调性：从队尾开始，移除所有值小于当前元素 $a_i$ 的索引
    • 插入当前元素：将当前元素索引加入队尾
    • ​记录结果: 当 $i \ge k - 1$ 时，队首元素即为窗口最大值
• 整体算法：

• 时间复杂度：$O(n)$（每个元素入队、出队各一次）

最长递增子序列

• 优化思路：维护一个潜在前缀列表 $sm$，其中 $sm[len]$ 表示长度为 $len$ 的递增子序列的最小末尾值
  • 由于该列表单调递增，查找过程可优化为二分搜索

• 算法步骤：
  • 初始化 $sm[0] = 0$
  • 对每个 $a_i$：
    • 二分查找使得 $a_i > sm[len]$ 的最大 $len$
    • 更新 $sm[len + 1] = a_i$
  • 输出更新过的最大 $len$
• 时间复杂度：$O(n \log n)$

图中 DP 示例

所有点对最短路径问题（Floyd-Warshall）

• 问题描述：
  • ​输入：带权有向图 $G(V,E)$，边权函数 $d(u,v)$
  • ​输出：所有顶点对之间的最短路径距离 $dist(u,v)$
• 子问题定义：$dist[k,u,v]$ 表示允许使用前 $k$ 个顶点作为中间点时，$u$ 到 $v$ 的最短距离
• 状态转移：

$$dist[k,u,v] = \min\{ dist[k-1, u, v], dist[k-1, u, k] + dist[k-1, k, v]\}$$

• 拓扑序：$k$ 从 $1$ 到 $n$
• 整体算法：

• 时间复杂度：$O(|V|^3)$

旅行商问题

• 问题描述：
  • ​输入：完全加权无向图 $G$，顶点间距离 $d(u,v)>0$
  • ​输出：访问所有顶点恰好一次的最小权重回路
• 子问题定义：$f[S, u, v]$ 表示恰好使用 $S \subset V$ 作为中间点时，$u$ 到 $v$ 的最短距离
  • 或固定起点 $u$，状态表示为 $f[S, v]$
• 状态转移：

$$f[S, u, v] = \min_{k \in S} \{f[S - \{k\}, u, k] + d(k, v)\}$$

• 拓扑序：按集合 $S$ 从小到大
• 时间复杂度：$O(n^22^n)$

树上的最大独立集

• 问题描述：
  • 输入：无向树 $T=(V,E)$
  • 输出：顶点集合 $S \subseteq V$，满足任意两顶点不相邻，且 $|S|$ 最大
• ​子问题定义：$f[u]$ 表示以 $u$ 为根的子树的最大独立集大小
• 状态转移：

$$f[v] = \max \left\{ \sum_{u \in children(v)} f[u], 1 + \sum_{u \in grandchildren(v)} f[u] \right\}$$

• 拓扑序：自底向上

• 时间复杂度：$O(n)$

网络流

问题及符号定义

• 最大流问题：
  • 输入：
    • ​有向图 $G(V, E)$，源点 $s$ 和汇点 $t$
    • ​对每条边 $e \in E$，定义容量 $c(e)$
  • 输出：从 $s$ 到 $t$ 的最大流量
• 规范定义：
  • ​流：$f: E \to \mathbb{R}_{\ge 0}$，对每条边 $e \in E$ 分配流量 $f(e)$
  • ​容量约束：对每条边 $e \in E$，满足 $f(e) \le c(e)$
  • ​流量守恒：对任意中间节点 $u \in V \setminus \{s, t\}$，满足
    $\sum_{(v, u) \in E} f(v, u) = \sum_{(u, w) \in E} f(u, w)$（流入流量 = 流出流量）
  • ​总流量：$v(f) = \sum_{(s, v) \in E} f(s, v)$
• 剩余网络：$G^f$，顶点集与原图相同，边集 $E_f$ 包含两类边：
  • ​正向边：若原边 $(u, v)$ 的流量 $f(u, v) < c(u, v)$，残留容量为 $c(u, v) - f(u, v)$
  • ​反向边：若原边 $(v, u)$ 的流量 $f(v, u) > 0$，残留容量为 $f(v, u)$

重要定理

• 整数流定理（Flow Integrality Theorom）：若网络所有边的容量均为整数，则存在整数最大流
• 最大流最小割定理（Max-Flow-Min-Cut Theorom）：最大流等于最小割，即

  $$\max_{f} v(f) = \min_{L, R} c(L, R)$$

  • Lemma 1：对任意流 $f$ 和任意割 $\{L, R\}$，$v(f) \le c(L, R)$，即任意割是任意流的上界
  • Lemma 2：存在一个割 $\{L, R\}$ 使得 Ford-Fulkerson 算法输出的流 $f$ 满足 $v(f) = c(L, R)$
    • 其中 $L$ 表示 $G^f$ 中从 $s$ 可达的顶点集合

▶

推论：求解最小割的方法

1. ​求解最大流 $f$ 并​构造剩余网络 $G^f$
2. ​令 $L$ = 在 $G^f$ 中从 $s$ 可达的顶点集合，$R$ = $V \setminus L$
3. 返回 $\{L, R\}$

应用题型

比赛胜负问题

• 问题描述：

• 转化为网络流：

二分图最大匹配问题

• 问题描述：
  • 输入：​二分图 $G = (A, B, E)$，其中：
    • $A$ 与 $B$ 为互不相交的顶点集合
    • $E \subseteq A \times B$ 为边集合
  • 输出：​最大匹配 $M \subseteq E$，满足：
    • $\forall u \in A \cup B$，最多存在一条边 $e \in M$ 与 $u$ 相连
    • $|M|$ 达到所有可能匹配中的最大值

• 转化为网络流：

算法及证明

Ford-Fulkerson 方法

• 算法步骤：
  • 初始化：设初始流 $f(e) = 0$，构建初始剩余网络 $G_f$
  • 迭代过程：
    • 寻找增广路径：在 $G_f$ 中找一条 $s \rightarrow t$ 路径 $p$
    • ​计算瓶颈容量：找出路径 $p$ 上残留容量的最小值 $b$
    • 更新流量：对路径 $p$ 中的每条边 $(u, v)$
      • 若为正向边，增加流量：$f(u, v)$ += $b$
      • 若为反向边，减少原边流量：$f(v, u)$ -= $b$
    • 更新残留网络：根据新流量 $f$ 重新构建 $G_f$
  • 终止条件：当残留网络中不存在 $s \to t$ 路径时，返回最大流 $f$

• 正确性证明：由最大流最小割定理保证
• 终止性：若所有容量均为有理数，会终止；若存在无理数，不一定终止
• 时间复杂度：$O(|E| \cdot f_{\max})$（要求所有容量为整数）
  • 最多 $f_{\max}$ 轮迭代，每轮迭代 $O(|E|)$ 时间

Edmonds-Karp 算法

• 改进点：用 BFS 选择增广路径
• 整体算法：

• 关键性质：
  • $G^f$ 中任意顶点 $u$ 到源点的距离 $dist(u)$ 单调不减
  • 每次增广导致 $G^f$ 中至少一条边被饱和（称 $G$ 中对应的原边为关键边）
  • 原边 $(u, v)$ 两次成为关键边后 $dist(u)$ 至少增加 $2$
    • $\mathrm{dist}^{i + j}(u) = \mathrm{dist}^{i + j}(v) + 1 \ge \mathrm{dist}^i(v) + 1 = \mathrm{dist}^i(u) + 2$

• 时间复杂度:
  • 每条边成为关键边的次数：$O(|V|)$
  • 总迭代次数：$O(|V| \cdot |E|)$
  • 每次迭代的时间：$O(|E|)$
  • 总时间复杂度：$O(|V| \cdot |E|^2)$

Dinic 算法

• 核心思路：每一轮将 $t$ 到源点的距离 $dist(t)$ 增大 $1$
• 相关概念：
  • 分层图 (Level Graph)：仅保留从源点出发按 BFS 层数递增的边
  • 阻塞流 (Blocking Flow)：分层图中无法再找到增广路径的流

• 算法步骤：

  • 初始化流 $f$ 为空，剩余网络 $G^f$ 为 $G$
  • 重复以下步骤，直到 $dist(t) = \infty$
    • 从 $G^f$ 构建分层图 $G_L^f$
    • 用 DFS 在分层图中寻找阻塞流
    • 更新流 $f$ 和残差网络 $G^f$

• 关键性质：

  • 每次 DFS 搜索后至少一条边被移除（关键边或回溯边）
  • $G_L^f$ 中所有长度为 $\mathrm{dist}^i(t)$ 的路均被阻塞，从而 $\mathrm{dist}^{i + 1}(t) > \mathrm{dist}^i(t)$

• 时间复杂度：

  • 每次搜索最多步数：$O(|V|)$
  • 每次迭代中搜索次数：$O(|E|)$
  • 每次迭代的时间：$O(|V| \cdot |E|)$
  • 迭代次数：$O(|V|)$
  • 总时间复杂度：$O(|V|^2 \cdot |E|)$

Hopcroft-Karp-Karzanov 算法

• 算法思想：Dinic 算法应用于二分图最大匹配问题（所有边容量为1）

• 时间复杂度：$O(|E| \cdot \sqrt{|V|})$
  • 寻找阻塞流：
    • 由于边容量均为 $1$，寻找阻塞流时每条边只会经过一次
    • 每次寻找阻塞流的时间复杂度为 $O(|E|)$
  • 迭代轮数：
    • 对每个非 $s$ 或 $t$ 的点，在 $G^f$ 中其入度或出度始终为 $1$
    • $G^f$ 中的最大流等于 $G^f$ 中点不相交（vertex-disjoint）路的数量
    • $\sqrt{|V|}$ 轮后，$G^f$ 中 $dist(t)$ 至少为 $\sqrt{|V|}$，$G^f$ 中最大流最多是 $\sqrt{|V|}$
    • 从而再过 $\sqrt{|V|}$ 轮后，算法终止，即总迭代轮数最多 $2 \sqrt{|V|}$

算法总结

算法	时间复杂度	核心思想	适用场景
Ford-Fulkerson	$O(\vert E \vert \cdot f_{max})$	任意增广路径	理论分析
Edmonds-Karp	$O(\vert V \vert \cdot \vert E \vert ^2)$	BFS 选择增广路径	稀疏图
Dinic	$O(\vert V \vert ^2 \cdot \vert E \vert)$	分层图 + 阻塞流	稠密图
Hopcroft-Karp-Karzanov	$O(\vert E \vert \cdot \sqrt{\vert V \vert})$	Dinic 在二分图中应用	二分图最大匹配

线性规划

LP 对偶与 LP 松弛

• LP 的标准型：

$$\begin{align*} \text{maximize} &\quad \bm{c}^T\bm{x} \\ \text{subject to} &\quad A\bm{x} \leq \bm{b} \\ &\quad \bm{x} \geq \bm{0} \end{align*}$$

• LP 的对偶问题：

$$\begin{align*} \text{minimize} &\quad \bm{b}^T\bm{y} \\ \text{subject to} &\quad A^T\bm{y} \geq \bm{c} \\ &\quad \bm{y} \geq \bm{0} \end{align*}$$

▶

一个原问题和对偶问题的例子

• 原问题：

$$\begin{array}{rrll}\text{maximize} & 4x_1 + 6x_2 \\\text{subject to} & x_1 + 2x_2 & \leq 10 \\& 3x_1 + 2x_2 & \leq 18 \\& x_1, x_2 & \geq 0\end{array}$$

• 对偶问题：

$$\begin{array}{rrll}\text{minimize} & 10y_1 + 18y_2 \\\text{subject to} & y_1 + 3y_2 & \geq 4 \\& 2y_1 + 2y_2 & \geq 6 \\& y_1, y_2 & \geq 0\end{array}$$

• 对偶定理

  • 弱对偶定理：对偶问题的目标值始终 $\ge$ 原始问题的目标值
  • 强对偶定理：若两者均有可行解，则最优目标值相等

• LP 松弛：将整数规划中 $x_i \in \{0,1\}$ 松弛为 $0 \leq x_i \leq 1$

• Primal Dual 分析：以“顶点覆盖”和“最大匹配问题”为例

  • 原问题：顶点覆盖

    $$\begin{align*} \text{minimize} &\quad \sum_{v \in V} x_v \\ \text{subject to} &\quad x_u + x_v \geq 1 &&\quad \forall (u,v) \in E \\ &\quad x_v \ge 0 &&\quad \forall v \in V \end{align*}$$

  • 对偶问题：最大匹配

    $$\begin{align*} \text{maximize} &\quad \sum_{e \in E} y_e \\ \text{subject to} &\quad \sum_{v \in N(u)} y_{(u, v)} \le 1&&\quad \forall u \in V \\ &\quad y_{(u, v)} \ge 0 &&\quad \forall (u, v) \in E \end{align*}$$

存在最优整数解的证明

• 核心思路：证明多面体 $P = \{\bm{x}: A\bm{x} \le \bm{b}\}$ 的所有顶点均为整数点
• 定理：如果 $A \in \mathbb{R}^{m \times n}$ 是全单模（totally unimodular）矩阵，$\bm{b}$ 是整数向量，那么多面体 $P = \{\bm{x}: A\bm{x} \le \bm{b}\}$ 的顶点均为整数
  • 全单模矩阵：如果矩阵 $A$ 的任何子方阵的行列式都等于$0$，$1$ 或 $-1$，那么 $A$ 是全单模矩阵
  • 性质：如果 $A$ 是全单模矩阵，那么 $A^T, \begin{bmatrix}I & A\end{bmatrix}, \begin{bmatrix}A & I\end{bmatrix}, \begin{bmatrix}I \\ A\end{bmatrix}, \begin{bmatrix}A \\ I\end{bmatrix}$ 都是全单模矩阵
• 归纳法证明：以“最大流最小割定理”的证明为例
  • 原问题：最大流

    $$\begin{align*} \text{maximize} &\quad \sum_{u:(s, u) \in E} f_{su} \\ \text{subject to} &\quad 0 \le f_{uv} \le c_{uv} &&\quad \forall (u, v) \in E \\ &\quad \sum_{v:(v, u) \in E} f_{vu} = \sum_{w:(u, w) \in E} f_{uw} &&\quad \forall u \in V \setminus \{s, t\} \end{align*}$$

  • 对偶问题：最小割

    $$\begin{align*} \text{minimize} &\quad \sum_{(u, v) \in E} c_{uv} y_{uv} \\ \text{subject to} &\quad y_{su} + z_u \ge 1 &&\quad \forall u: (s, u) \in E \\ &\quad y_{vt} - z_v \ge 0 &&\quad \forall v:(v, t) \in E \\ &\quad y_{uv} - z_u + z_v \ge 0 &&\quad \forall (u, v) \in E, u \neq s, v \neq t \\ &\quad y_{uv} \ge 0 &&\quad \forall (u, v) \in E \end{align*}$$

  • 证明对偶问题有整数最优解：归纳法证明 $Z$ 是全单模矩阵

NP 完全

Karp 归约与证明 NP 完全

• 常见的 NP 完全问题：

▶

SAT 问题

给定一个 CNF 表达式 $\phi$，判断其是否存在使 $\phi$ 为真的赋值。

▶

3SAT 问题

给定一个 3-CNF 表达式 $\phi$，判断其是否存在使 $\phi$ 为真的赋值。3-CNF 表达式是指每个字句只包含最多三个文字的 CNF。

▶

顶点覆盖问题

给定一个无向图 $G = (V, E)$ 和正整数 $k$，判断是否 $G$ 存在大小为 $k$ 的顶点覆盖。对一个无向图 $G = (V, E)$，如果每条边都至少有一个端点在 $S \subseteq V$中，那么 $S$ 是 $G$ 的一个顶点覆盖。

▶

独立集问题

给定一个无向图 $G = (V, E)$ 和正整数 $k$，判断是否 $G$ 存在大小为 $k$ 的独立集。对一个无向图 $G = (V, E)$，如果顶点集合 $S \subseteq V$ 中任意两个顶点都不相邻，那么 $S$ 是 $G$ 中的一个独立集。

▶

团问题

给定一个无向图 $G = (V, E)$ 和正整数 $k$，判断是否 $G$ 存在大小为 $k$ 的团。对一个无向图 $G = (V, E)$，如果顶点集合 $S \subseteq V$ 中任意两个顶点都相邻，那么 $S$ 是 $G$ 中的一个团。

▶

支配集问题

给定一个无向图 $G = (V, E)$ 和正整数 $k$，判断是否 $G$ 存在大小为 $k$ 的支配集。对一个无向图 $G = (V, E)$ 和顶点集合 $S \subseteq V$，如果每个不在 $S$ 中的顶点都存在 $S$ 中的顶点与它相邻，那么 $S$ 是 $G$ 的一个支配集。

▶

子集和问题

给定一些整数 $S = \{a_1, \dots, a_n\}$ 和正整数 $k$，判断是否存在 $T \subseteq S$ 使得 $\sum_{a_i \in T} a_i = k$。

▶

划分问题

给定一些整数 $S = \{a_1, \dots, a_n\}$ 和正整数 $k$，判断是否能将 $S$ 划分为 $A$ 和 $B$ 使得 $\sum_{a \in A} a = \sum_{b \in B} b$。

▶

哈密顿路径问题

给定一个无向图 $G = (V, E)$，判断 $G$ 是否存在哈密顿路径。对一个无向图 $G = (V, E)$，哈密顿路径指一条包含每个顶点恰好一次的路径。

• 证明 NP：问题的正确实例（yes instance）能在多项式时间内被验证
• 证明 NP 完全的步骤：
  1. 证明 $f$ 是 NP 问题
  2. 对一个 NP 完全问题 $g$，给出 $g \le_k f$ 的归约过程
     • 这表明 $f$ 的难度略高于 $g$
  3. 证明 $g$ 的正确实例映射到 $f$ 的正确实例
  4. 证明 $g$ 的错误实例映射到 $f$ 的错误实例
     • 或证明逆否命题，即映射到 $f$ 的正确实例的 $g$ 实例都是正确的

NP 完全归约示例

SAT 归约到 3SAT

• 方法：引入新变量，将长字句拆分为最多三个文字的短字句
• 例子：

$$\phi = (x_1 \lor x_2 \lor \lnot x_3 \lor \lnot x_4 \lor x_5 \lor x_6)$$

$$\phi' = (x_1 \lor x_2 \lor y_1) \land (\lnot y_1 \lor \lnot x_3 \lor y_2) \land (\lnot y_2 \lor \lnot x_4 \lor y_3) \land (\lnot y_3 \lor x_5 \lor x_6)$$

• 解释：$\phi$ 是一个正确的 SAT 实例当且仅当 $\phi'$ 是一个正确的 3SAT 实例

3SAT 归约到独立集

• 方法：
  1. 对每个字句，构造三角形，其中每个顶点代表一个文字
  2. 连接代表互为否定文字的顶点
  3. 设独立集问题 $k$ 为字句数
• 解释：要证明构造的实例和原实例的正确性相同

独立集归约到顶点覆盖

• 方法：$S$ 是 $G$ 的独立集 $\iff$ $V - S$ 是 $G$ 的顶点覆盖

独立集归约到团问题（Clique）

• 方法：$S$ 是 $G$ 的独立集 $\iff$ $S$ 是 $\bar{G}$ 中的团

顶点覆盖归约到支配集

• 基本思路：在每条边中间插入一个顶点，覆盖边转化为了覆盖中间的顶点
• 修复及最终方法：

• 完整证明：

First of all, DominatingSet is in NP, as a dominating set $S$ can be served as a certificate, and it can be verified in polynomial time whether $S$ is a dominating set and whether $|S|=k$.

To show that DominatingSet is NP-complete, we present a reduction from VertexCover. Given a VertexCover instance $(G=(V,E),k)$, we construct a DominatingSet instance $(G^{\prime}=(V^{\prime},E^{\prime}),k^{\prime})$ as follows.

The vertex set is $V^{\prime}=V\cup E$, which is defined as follows. For each vertex $v\in V$ in the VertexCover instance, construct a vertex $\overline{v}\in\overline{V}\subseteq V^{\prime}$; for each edge $e\in E$ in the VertexCover instance, construct a vertex $w_{e}\in\overline{E}\subseteq V^{\prime}$.

The edge set $E^{\prime}$ is defined as follows. For each edge $e=(u,v)$ in the VertexCover instance, build two edges $(\overline{u},w_{e}),(\overline{v},w_{e})\in E^{\prime}$. For any two vertices $\overline{u},\overline{v}$ in $V$, build an edge $(\overline{u},\overline{v})$.

Define $k^{\prime}=k$.

Suppose $(G=(V,E),k)$ is a yes VertexCover instance. There exists a vertex cover $S\subseteq V$ with $|S|=k$. We will prove $\overline{S}$ corresponding $S$ is a dominating set in $G'$.

For each vertex in $\overline{V}$, it is covered by any vertex in $\overline{S}$ as $\overline{V}$ forms a clique.

For each vertex $w_{e}$ in $\overline{E}$, let $e=(u,v)\in E$ be the corresponding edge in the VertexCover instance. We have either $u\in S$ or $v\in S$ (or both), as $S$ is a vertex cover. This implies either $\overline{u}\in\overline{S}$ or $\overline{v}\in\overline{S}$ (or both), which further implies $w_{e}$ is covered as $(\overline{u},w_{e}),(\overline{v},w_{e})\in\overline{E}$ by our construction.

Since $|\overline{S}|=|S|=k=k'$, the DominatingSet instance we constructed is a yes instance.

希望大家考试取得好成绩！