NP 理论与近似算法 (NP & Approximation)

NPC 的证明方法

证明一个问题是 NPC：

属于 NP：给出一个非确定性多项式时间算法（即"猜一个解、多项式时间验证"）；
NP-hard：从已知 NP-hard 问题（SAT、3-SAT…）多项式归约到它。

已知 NPC 问题

Partition：把数集划分为两个和相等的子集。可由 Subset-sum 归约，且是 0-1 背包的受限情形（见 06_knapsack 的 416 题——所以那道题只能用伪多项式 DP，没有多项式算法）。
顶点覆盖（判定问题）、最大团、最大独立集、Hamiltonian 环、旅行商等。

无向 Hamiltonian 环（有向 → 无向的归约实例）

从 Directed Hamiltonian Cycle（可由 3-SAT 归约证明 NP-hard）归约：对每条有向边用一个"三段结构"表示。构造 $G'$ ：

V' = \{v^{in}, v^{mid}, v^{out} \mid v \in V\} \\ E' = \{(u^{out}, v^{in}) \mid \langle u, v \rangle \in E\} \cup \{(v^{in}, v^{mid}), (v^{mid}, v^{out}) \mid v \in V\}

$\Rightarrow$ ：G 有向 HC → 把对应边连起来即 G' 的无向 HC；
$\Leftarrow$ ：G' 中经过 $v^{mid}$ 的唯一方式是同时经过 $(v^{in}, v^{mid})$ 与 $(v^{mid}, v^{out})$ ，因此可找回 G 中对应的有向环。

反例说明不能省掉 $v^{mid}$ 只用 in/out 两点（存在不是有向 HC 对应的无向环）。

Strongly Independent Set（独立集变体的归约）

定义：I 是强独立的，若任意 u, v ∈ I 之间无边、也不存在长度 2 的路径。证明 NPC：对 G 的每条边 e 细分一个新点 $v_e$ ，并把所有新点连成团。则 G 有 k 独立集 ⇔ G' 有 k 强独立集（新点在团里，任意两点间必有长 2 路径，故强独立集不可能含新点）。

近似算法

近似算法针对组合优化问题：

最小顶点覆盖：贪心——任取一条边，两端都加入 V'，删去其关联边，直到无边。这是常数比为 2 的多项式近似（紧实例：k 条互不相连的边）。顶点覆盖的判定问题是 NPC。
最大团 & 最大独立集：目前认为不存在常数近似比的近似算法。