NP 完全(2)：归约与优化

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为NP完全问题（进阶），包括Karp归约等。

以“顶点覆盖归约到支配集”为例

归约方法

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

证明过程

• 一般思路：证明 $f$ 是 NP 完全问题
  1. 证明 $f$ 是 NP 问题
  2. 对一个 NP 完全问题 $g$，给出 $g \le_k f$ 的归约过程
  3. 证明 $g$ 的正确实例映射到 $f$ 的正确实例
  4. 证明 $g$ 的错误实例映射到 $f$ 的错误实例
     • 或证明逆否命题，即映射到 $f$ 的正确实例的 $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.

注：本文中所有图片均来自张宇昊老师的课程PPT。