Intractability 计算复杂性 / NP-Complete Problems NP完备性理论

1.理解什么是多项式归约polynomial-time reduction；

2.从一个问题A多项式归约到另一个问题B时，掌握针对问题A的任意实例构造问题B的实例的方法，重点掌握的归约包括：

图问题：

• Vertex-Cover 顶点覆盖 ≡p lndependent Set 独立集
• Vertex-Cover 顶点覆盖 ≤p Set-Cover 集合覆盖
• Vertex-Cover 顶点覆盖 ≤p Dominating-Set 支配集

约束满足问题：

• 3-SAT 三元可满足性 ≤p Independent Set 独立集

路径问题：

• Ham-Cycle 哈密顿回路 ≤p TSP 旅行商
• Ham-Cycle 哈密顿回路 ≤p Longest-Path 最长路径

图着色问题：

• 3-Color 三着色 ≤p k-Color k着色 (k > 3)

数值问题：

• Subset-Sum 子集和 ≤p Knapsack 背包
• Subset-Sum 子集和 ≤p Partition 划分
• Partition 划分 ≤p k-Load-Balance k负载均衡

3.要求掌握同一个问题的最优化问题如何多项时间归约到该问题的判断问题（自身归约），例如：

• Vertex-Cover 顶点覆盖问题
• Hamilton Cycle 哈密顿回路问题
• 3-Color 三着色问题

典型考题：作业2中的第2题

4.掌握如果P≠NP ，P、NP和NPC三个集合之间的关系， 以及NP问题定义的非对称性；

5.记住证明一个问题属于NPC的基本步骤；

6.能证明给定的问题是NP完全问题，典型考题：作业2中的第3题。

Classify problems 问题分类

P（P问题）

P. Decision problems for which there exists a poly-time algorithm.
P问题：存在多项式时间求解算法的判断问题

NP（NP问题）

NP. Decision problems for which there exists a poly-time certifier.
NP问题：存在多项式时间内的证据，可以证明”是“的判断问题

问题：是否存在满足条件的X
证据：找到了X
证据在多项式时间内验证满足了条件，证明了”是“存在X

Proposition. P ⊆ NP.

Pf. Consider any problem X ∈ P.

• By definition, there exists a poly-time algorithm A(s) that solves X.
• Certificate t = ε, certifier C(s, t) = A(s).

EXP（EXP问题）

EXP. Decision problems for which there exists an exponential-time algorithm.
EXP问题：存在指数时间求解算法的判断问题

Proposition. NP ⊆ EXP.

Pf. Consider any problem X ∈ NP.

• By definition, there exists a poly-time certifier C(s, t) for X, where certificate t satisfies |t| ≤_P(|s|) for some polynomial p(⋅).
• To solve instance s, run C(s, t) on all strings t with |t| ≤_P(|s|).
• Return yes iff C(s, t) returns yes for any of these potential certificates.

NP-complete（NP完全问题）

NP-complete. A problem Y ∈ NP with the property that for every problem X ∈ NP, X ≤_P Y.
NP完全问题：是一个NP问题，且所有NP问题都可以多项式归约到这个问题

co-NP（co-NP问题）

co-NP. Complements of decision problems in NP.
co-NP问题：NP判断问题的互补问题（反问题），可以在多项式时间内验证”否“的判断问题

NP-hard（NP难问题）

NP-hard. [Bell Labs, Steve Cook, Ron Rivest, Sartaj Sahni]
A problem such that every problem in NP poly-time reduces to it.
NP难问题：所有NP问题都可以多项式归约到这个问题（不一定是NP问题）

Poly-time reductions 多项式归约

Reduction. Problem X polynomial-time (Cook) reduces to problem Y if arbitrary instances of problem X can be solved using:
归约：问题X多项式归约到问题Y，说明X的任意实例可以使用以下方法解决：

• Polynomial number of standard computational steps, plus
  多项式次基础操作，以及
• Polynomial number of calls to oracle that solves problem Y.
  多项式次调用问题Y的解

Notation. X ≤_PY.
记作：X≤_PY

Note. We pay for time to write down instances of Y sent to oracle ⇒ instances of Y must be of polynomial size.
注意：问题Y的实例必须也是多项式大小的

Novice mistake. Confusing X ≤_P Y with Y ≤_P X.
易错：不要搞混 X ≤_P Y 和 Y ≤_P X

应用

设计算法

Design algorithms. If X ≤_P Y and Y can be solved in polynomial time, then X can be solved in polynomial time.
设计算法：如果X ≤_P Y，而且Y能够在多项式时间内求解，那么X也能在多项式时间内求解

说明难解性

Establish intractability. If X ≤_P Y and X cannot be solved in polynomial time, then Y cannot be solved in polynomial time.
说明难解性：如果X ≤_P Y，而且X无法在多项式时间内求解，那么Y也不能在多项式时间内求解

说明多项式等价

Establish equivalence. If both X ≤_P Y and Y ≤_P X, we use notation X ≡_P Y. In this case, X can be solved in polynomial time iff Y can be.
说明等价：如果X ≤_P Y且Y ≤_P X，那么记作X ≡_P Y（多项式等价），X能在多项式时间内求解当且仅当Y能在多项式时间内求解

例如：排序≡_P最大值

★证明一个问题是NP完全问题的主要步骤

• Step 1. 证明该问题是NP问题.
• Step 2. 找到一个已知的NP完全问题X.
• Step 3. 证明问题X可以多项式归约到该问题.

归约的本质

Bottom line. Reductions classify problems according to relative difficulty.
原则：归约根据相对难度分类问题

多项式归约的路径

Packing and covering problems 填充和覆盖问题

问题 > Independent set 独立集

INDEPENDENT-SET. Given a graph G = (V, E) and an integer k, is there a subset of k (or more) vertices such that no two are adjacent?
独立集问题：给定一个图G = (V, E)和整数k，是否存在k个（或以上）顶点的子集，其中任意两个顶点不相邻

问题 > Vertex cover 顶点覆盖

VERTEX-COVER. Given a graph G = (V, E) and an integer k, is there a subset of k (or fewer) vertices such that each edge is incident to at least one vertex in the subset?
顶点覆盖问题：给定一个图G = (V, E)和整数k，是否存在k个（或以下）顶点的子集，任意边至少一个其中的顶点相连

★Vertex cover and independent set reduce to one another 顶点覆盖 和 独立集 相互归约

Theorem. INDEPENDENT-SET ≡_P VERTEX-COVER.
定理： 顶点覆盖问题 和 独立集问题 多项式等价

Pf. We show S is an independent set of size k iff V − S is a vertex cover of size n – k.
证明：S是k大小的独立集当且仅当V − S是n – k大小的顶点覆盖

⇒ 充分性

• Let S be any independent set of size k.
  S是k大小的任意独立集
• V − S is of size n – k.
  V − S是n – k大小的顶点集
• Consider an arbitrary edge (u, v) ∈ E.
  对于E中任意边(u, v)
• S independent ⇒ either u ∉ S, or v ∉ S, or both.
  ⇒ either u ∈ V − S, or v ∈ V − S, or both.
  由于S是独立的，所以边(u, v)的两个顶点不可能同时出现在S中
  所以边(u, v)的两个顶点至少一个出现在V − S中
• Thus, V − S covers (u, v).
  所以V − S覆盖率任意边(u, v)

⇐ 必要性

• Let V − S be any vertex cover of size n – k.
  V − S是n – k大小的任意顶点覆盖
• S is of size k.
  S是k大小的顶点集
• Consider an arbitrary edge (u, v) ∈ E.
  对于E中任意边(u, v)
• V − S is a vertex cover ⇒ either u ∈ V − S, or v ∈ V − S, or both.
  ⇒ either u ∉ S, or v ∉ S, or both.
• 由于V − S是顶点覆盖，所以边(u, v)的两个顶点至少一个出现在V − S中
  所以边(u, v)的两个顶点不可能同时出现在S中
• Thus, S is an independent set.
  所以S是独立集

问题 > Set cover 集合覆盖

SET-COVER. Given a set U of elements, a collection S of subsets of U, and an integer k, are there ≤ k of these subsets whose union is equal to U ?
顶点覆盖问题：给定全集U，一组U的子集合S，整数k，是否存在不超过k个子集合，这些子集和的并集是全集U

★Vertex cover reduces to set cover 顶点覆盖 归约到 集合覆盖

Theorem. VERTEX-COVER ≤_P SET-COVER.
定理： 顶点覆盖归约到集合覆盖

Pf. Given a VERTEX-COVER instance G = (V, E) and k, we construct a SET-COVER instance (U, S, k) that has a set cover of size k iff G has a vertex cover of size k.
证明：对于任意顶点覆盖的实例G = (V, E)以及k，构造一个集合覆盖的实例(U, S, k)，这个实例有k大小的集合覆盖当且仅当G有k大小的顶点覆盖

Construction.
构造

• Universe U = E.
  全集U=边集E
• Include one subset for each node v ∈ V : S_v = {e ∈ E : e incident to v }.
  对于V中每个节点v，构造一个子集S_v包括与节点v相连的边e

Lemma. G = (V, E) contains a vertex cover of size k iff (U, S, k) contains a set cover of size k.
引理：图G = (V, E)有k大小的顶点覆盖当且仅当(U, S, k)有k大小的集合覆盖

Pf. ⇒ Let X ⊆ V be a vertex cover of size k in G.
证明充分性：设X是图G中大小为k的顶点覆盖

• Then Y = { S_v : v ∈ X } is a set cover of size k.
  那么S_v是大小为k的集合覆盖

Pf. ⇐ Let Y ⊆ S be a set cover of size k in (U, S, k).
证明必要性：设Y是大小为k的集合覆盖

• Then X = { v : S_v ∈ Y } is a vertex cover of size k in G.
  那么X是图G中大小为k的顶点覆盖

问题 > Dominating set 支配集

支配集（Dominating-set）问题：给定无向图G和正整数k，问图G中是否存在k个顶点的子集S，使得对于图G中的任意顶点v，要么v∈S，要么v至少与S中的至少一个顶点相邻。

★Vertex cover reduces to dominating set 顶点覆盖 归约到 支配集

证明：
对给定的无向图G，作如下处理：对于图G的任意边(u, v)，添加一个点w_uv，使得该边的两个顶点u、v分别与w_uv相邻，得到一个新的无向图G’。

i) 若原无向图G存在一个顶点覆盖S，且S满足|S|<= k，则S也可以作为图G’的一个满足条件的支配集。原因如下：

假设S不是图G’的支配集，即存在点w∈V(G')，使得w∉S且w不与S中的任意顶点相邻。由于图G连通，则必然存在边（u，w）满足u∉S。显然边（u，w）是在原图上添加的一条辅助边，否则，根据条件“S是G的一个顶点覆盖”得“边（u，w）至少有一个顶点属于S”，与“w∉S且u∉S”矛盾。则w为辅助顶点。

设w对应的边为（u，v），由S是G的一个覆盖，且（u，v）边的顶点u不属于S，则顶点v必然属于S。w与v相邻，即w与S中的一个顶点（v）相邻，与假设矛盾。则证明假设不成立。

则得证“若S为无向图G的一个顶点覆盖，且|S|<=b，则S是图G’的支配集”。

ii) 若无向图G’存在一个支配集D，且D满足|D|<=k，则图G存在满足条件的顶点覆盖S。原因如下：

对于G’的边（u，v）及其辅助点w，

若w∉D，则D也可以看做原图G的一个顶点覆盖S；若w∈D且u、v∉D，则将D中的顶点w替换成顶点u或v，可以得到原图G的一个顶点覆盖S；

若w∈D且u∈D、v∉D（或u∉D、v∈D），则将D中的顶点w删除，可以得到原图G的一个顶点覆盖S；

若w∈D且u、v∈D，则将D中的顶点w删除，可以得到原图G的一个顶点覆盖S；

则得证“若无向图G’存在一个支配集D满足|D|<=b，则图G必然存在顶点覆盖S，且|S|<=|D|<=b”。

综上所述，任何顶点覆盖问题，都可以规约到支配集问题。由于顶点覆盖问题可以规约到支配集问题（Vertex-set problem -> Dominating-set problem），且顶点覆盖问题是NP完全问题，则支配集问题为NP完全问题

例题：删除k个点使得剩余图上没有三角形

(2018)给出一个图和一个整数k，问是否可以在这个图上删除k个点使得剩余图上没有三角形(含有3个顶点的圈)。证明这个问题是NP完全的。

答：从点覆盖问题规约过来（2 分）。

对于一个点覆盖实例 G，构造一个该问题实例 G’；（1 分）
对 G 中每一条边 ab，都添加一个新的顶点 c 然后连成三角形 abc。（4 分）
说明 G 存在大小为 k 的点覆盖当且仅当 G’ 存在一个大小为 k 的解。（3 分）

证明充分性：若 G 存在大小为 k 的点覆盖，那么G中删除所有点覆盖中的顶点就会删除所有边，G'中只剩新加的边，这些边不可能构成三角形，即 G’ 存在一个大小为 k 的解

证明必要性：若 G’ 存在一个大小为 k 的解，则添加的三角形一定会被破坏

• 如果删除的节点是a或b，则覆盖了边ab
• 如果删除的节点是c，则将c与a或b替换，覆盖了边ab

这样删除的节点会覆盖所有边，即 G 存在大小为 k 的点覆盖

Constraint satisfaction problems 约束满足问题

Satisfiability 可满足性

Literal. A Boolean variable or its negation.
字面量：一个布尔变量或者它的反

$x_i$ or $\overline{x_i}$

Clause. A disjunction of literals.
子句：一组字面量的析取（∨）

Conjunctive normal form (CNF). A propositional formula Φ that is a conjunction of clauses.
连接范式：一个命题公式Φ是子句的合取（∧）

SAT. Given a CNF formula Φ, does it have a satisfying truth assignment?
可满足性问题：给定一个连接范式Φ，是否存在可满足的真值指派

3-SAT. SAT where each clause contains exactly 3 literals (and each literal corresponds to a different variable).
三元可满足性问题：每个子句含正好3个字面量的可满足性问题，每个字面量对应一个不同的变量

Satisfiability is hard 可满足性问题是困难的

Scientific hypothesis. There does not exists a poly-time algorithm for 3-SAT.

P vs. NP. This hypothesis is equivalent to P ≠ NP conjecture.

★3-satisfiability reduces to independent set 三元可满足性问题归约到独立集问题

Theorem. 3-SAT ≤ P INDEPENDENT-SET.
定理：三元可满足性问题归约到独立集问题

Pf. Given an instance Φ of 3-SAT, we construct an instance (G, k) of INDEPENDENT-SET that has an independent set of size k = |Φ| iff Φ is satisfiable.
证明：对于任意一个三元可满足性问题Φ，构造一个独立集问题的实例(G, k)，这个实例有大小为|Φ|的独立集当且仅当Φ是可满足的

Construction. 构造

• G contains 3 nodes for each clause, one for each literal.
  对于每个子句，图G有三个节点代表每个字面量
• Connect 3 literals in a clause in a triangle.
  同一子句的三个字面量连成三角形
• Connect literal to each of its negations.
  连接每个字面量和它的反

Lemma. Φ is satisfiable iff G contains an independent set of size k = |Φ|.
引理：Φ是可满足的当且仅当G有大小为|Φ|的独立集

Pf. ⇒ Consider any satisfying assignment for Φ.
证明充分性：设存在可满足的真值指派

• Select one true literal from each clause/triangle.
  对于每个三角形/子句，选择一个真字面量
• This is an independent set of size k = |Φ|.
  这些字面量构成这个图的独立集

Pf. ⇐ Let S be independent set of size k.
证明必要性：S是|Φ|个顶点的独立集

• S must contain exactly one node in each triangle.
  每个三角形有且只有一个顶点
  如果一个三角形中没有顶点，无法覆盖三角形的边
  如果一个三角形顶点多于1个，就会有其他三角形没有顶点
  因为是独立集，所有不可能有字面量和它的反都选上
• Set these literals to true (and remaining literals consistently).
  令这些顶点为真
• All clauses in Φ are satisfied.
  所有子句都满足了

Review 小结

Basic reduction strategies.
归约的基本策略

• Simple equivalence: INDEPENDENT-SET ≡_P VERTEX-COVER.
  简单等价：独立集≡_P顶点覆盖
• Special case to general case: VERTEX-COVER ≤_P SET-COVER.
  特殊情况化为一般情况
• Encoding with gadgets: 3-SAT ≤_P INDEPENDENT-SET.
  使用小组件

Transitivity. If X ≤_P Y and Y ≤_P Z, then X ≤_P Z.
传递性

Pf idea. Compose the two algorithms.
证明思路：组合两个算法

Ex. 3-SAT ≤ _P INDEPENDENT-SET ≤ _P VERTEX-COVER ≤ _P SET-COVER.
例如

Self-Reducibility 自身归约

Decision, Search, and Optimization Problems 判断、搜索和最优化问题

Decision problem. Does there exist a vertex cover of size ≤ k ?
判断问题：是否存在大小不超过k的顶点覆盖

Search problem. Find a vertex cover of size ≤ k.
搜索问题：找到大小不超过k的顶点覆盖

Optimization problem. Find a vertex cover of minimum size.
最优化问题：找到最小的顶点覆盖

Goal. Show that all three problems poly-time reduce to one another.
目标：事实证明所有三个问题都可以多项式归约到另一个

★Optimization problem reduces to decision version 最优化问题归约到判断问题

Self-reducibility. Optimization problem ≤_P decision version.
自身归约：最优化问题归约到判断问题

• Applies to all (NP-complete) problems in this chapter.
  适用于所有这章讲的（NP完全）问题
• Justifies our focus on decision problems.
  说明我们可以只关注决策问题

★找到最小的顶点覆盖

Ex: to find min cardinality vertex cover.
例如：（最优化问题）找到最小的顶点覆盖

• (Binary) search for cardinality k* of min vertex cover.
  （二分）查找的最小顶点覆盖的个数k*
  不断询问是否存在k个顶点的顶点覆盖，直到求出存在的最小值k*
• Find a vertex v such that G - { v } has a vertex cover of size ≤ k* - 1.
  找到一个顶点v使得去掉这个顶点的图G - { v }有不超过k* - 1个顶点的顶点覆盖
  • any vertex in any min vertex cover will have this property
    在任何顶点覆盖中任何顶点都会有这个性质
• Include v in the vertex cover.
  在顶点覆盖中包含顶点v
• Recursively find a min vertex cover in G - { v }. (delete v and all incident edges)
  递归地在剩下的图G - { v }中寻找顶点覆盖

★找到简单无向图的哈密尔顿圈

(2020)如果存在判断任意简单无向图是否存在哈密尔顿圈的多项式时间算法，请你设计构造任意简单无向图的哈密尔顿圈（如果存在的话）的多项式时间算法。(8分)

算法：

S初始化为空集；

首先判断图G中是否存在哈密尔顿圈，如果不存在则算法结束，如果存在则继续寻找哈密尔顿圈；

For every edge e in G {

如果G – {e}中不存在哈密尔顿圈，则将e添加到集合S中；

否则G = G – {e}；

} 最终所得集合S中的所有边构成图G的哈密尔顿圈。

★找到一个可行的三着色

(2018)对于三着色问题（对一个图的顶点进行三种颜色着色使得相邻两个点的颜色不一样)，若存在一个多项式时间算法判断一个图是否可以三着色，则存在一个多项式时间算法对可以进行三着色的图找到一个可行的三着色。(8分)

解法一：不断加边进去然后进行判断，直到不能加边为止。这样三种颜色的点就是图中三个独立集。

解法二：不断将两个不相邻的点合并成一个点然后进行判断，直到不能再合并为止。最后剩下三个点。

Sequencing problems 排序问题

问题 > Hamilton cycle 哈密尔顿回路

HAMILTON-CYCLE. Given an undirected graph G = (V, E), does there exist a cycle Γ that visits every node exactly once?
哈密尔顿回路问题：给定一个无向图G = (V, E)，是否存在一个回路Γ恰好通过每个节点一次

问题 > Directed Hamilton cycle 有向哈密尔顿回路

DIRECTED-HAMILTON-CYCLE. Given a directed graph G = (V, E), does there exist
a directed cycle Γ that visits every node exactly once?
有向哈密尔顿回路问题：给定一个有向图G = (V, E)，是否存在一个回路Γ恰好通过每个节点一次

Directed Hamilton cycle reduces to Hamilton cycle 有向哈密尔顿回路问题 归约到 哈密尔顿回路问题

Theorem. DIRECTED-HAMILTON-CYCLE ≤ P HAMILTON-CYCLE.
定理：有向哈密尔顿回路问题归约到哈密尔顿回路问题

Pf. Given a directed graph G = (V, E), construct a graph Gʹ with 3n nodes.
证明：对于任意一个n个节点的有向图G = (V, E)，构造一个3n个节点的无向图Gʹ

Lemma. G has a directed Hamilton cycle iff Gʹ has a Hamilton cycle.
引理：有向图G有哈密尔顿回路当且仅当无向图Gʹ有哈密尔顿回路

Pf. ⇒ 证明充分性：

• Suppose G has a directed Hamilton cycle Γ.
  假设有向图G有哈密尔顿回路Γ
• Then Gʹ has an undirected Hamilton cycle (same order).
  则无向图Gʹ也有相同顺序哈密尔顿回路

Pf. ⇐ 证明必要性：

• Suppose Gʹ has an undirected Hamilton cycle Γʹ.
  假设无向图Gʹ有哈密尔顿回路Γʹ
• Γʹ must visit nodes in Gʹ using one of following two orders:
  回路Γʹ必须以下面两种顺序之一经过无向图Gʹ
  • …, black, white, blue, black, white, blue, black, white, blue, …
    蓝黑白
  • …, black, blue, white, black, blue, white, black, blue, white, …
    白黑蓝
• Black nodes in Γʹ comprise either a directed Hamilton cycle Γ in G, or reverse of one.
  无向哈密尔顿回路Γʹ中的黑节点组成了在G中的哈密尔顿回路Γ，或者组成了在G中的哈密尔顿回路Γ的反向

3-satisfiability reduces to directed Hamilton cycle 三元可满足性问题 归约到 有向哈密尔顿回路问题

Theorem. 3-SAT ≤_P DIRECTED-HAMILTON-CYCLE.
定理：三元可满足性问题归约到有向哈密尔顿回路问题

Pf. Given an instance Φ of 3-SAT, we construct an instance G of DIRECTED-HAMILTON-CYCLE that has a Hamilton cycle iff Φ is satisfiable.
证明：对于任意给定的三元可满足性问题实例Φ，可以构造一个有向哈密尔顿回路问题的实例G，G存在有向哈密尔顿回路当且仅当Φ可满足

Construction overview. Let n denote the number of variables in Φ. We will construct a graph G that has 2ⁿ Hamilton cycles, with each cycle corresponding to one of the 2ⁿ possible truth assignments.
构造概述：n表示Φ中的变量个数。构造一个含有2ⁿ个哈密尔顿回路的图G，每个哈密尔顿回路代表2ⁿ个之一真值指派

Construction. Given 3-SAT instance Φ with n variables x_i and k clauses.
构造：对于任意给定的n个变量x_i和k个子句的三元可满足性问题实例Φ

• Construct G to have 2ⁿ Hamilton cycles.
  构造一个含有2ⁿ个哈密尔顿回路的图G
• Intuition: traverse path i from left to right ⇔ set variable x_i = true.
  直觉：从左到右穿过路径i等价于把变量x_i的值赋为真

• For each clause: add a node and 2 edges per literal.
  对于每个子句：添加一个节点，每个变量添加两条边
  • 如果变量x_i出现在子句中，边从左到右
  • 如果变量x_i的反出现在子句中，边从右到左

Lemma. Φ is satisfiable iff G has a Hamilton cycle.
引理：Φ是可满足的当且仅当G存在哈密尔顿回路

Pf. ⇒ 证明充分性：

• Suppose 3-SAT instance Φ has satisfying assignment x*.
  假设三元可满足性问题实例Φ有可满足的真值指派x*

• Then, define Hamilton cycle Γ in G as follows:
  那么，这样定义图G的哈密尔顿回路Γ：

  • if x*_i = true, traverse row i from left to right
    如果x*_i为真，从左到右穿过第i行

  • if x*_i = false, traverse row i from right to left
    如果x*_i为假，从右到左穿过第i行

• for each clause C_j , there will be at least one row i in which we are going in “correct” direction to splice clause node C_j into cycle (and we splice in C_j exactly once)
  对于每个子句节点C_j，至少有一行i，在这行中可以以正确地方向将节点C_j拼接进回路（每个节点恰好一次拼接进回路）

Pf. ⇐ 证明必要性：

• Suppose G has a Hamilton cycle Γ.
  假设图G有哈密尔顿回路Γ

• If Γ enters clause node C_j , it must depart on mate edge.
  如果回路Γ进入了子句节点C_j，它一定会从配对边出来

  • nodes immediately before and after C_j are connected by an edge e ∈ E
    紧挨着C_j之前和之后地节点使用一条来自E的边e相连
  • removing C_j from cycle, and replacing it with edge e yields Hamilton cycle on G – { C_j }
    将C_j从回路中移除，将其替换为边e，将得到一个图G – { C_j }的哈密尔顿回路

• Continuing in this way, we are left with a Hamilton cycle Γʹ in G – { C₁ , C₂ , …, C_k }.
  不断重复上述步骤，将剩下一个在图G – { C₁ , C₂ , …, C_k }中的哈密尔顿回路Γʹ

• Set x*_i = true if Γʹ traverses row i left-to-right; otherwise, set x*_i = false.
  如果Γʹ从左到右穿过第i行，令x*_i为真，否则令x*_i为假

• traversed in “correct” direction, and each clause is satisfied.
  以正确的方向穿过每行，每个子句都能够满足

例题：奇数个结点和偶数个结点的哈密尔顿圈 相互归约（与<哈密尔顿回路问题>归约到<最长路径问题>类似）

(2020)

• 判定问题A:给定包含奇数个结点的简单无向图，判断其是否包含哈密尔顿圈;
• 判定问题B:给定包含偶数个结点的简单无向图，判断其是否包含哈密尔顿圈;

证明问题A可多项式归约到问题B。(8分)

给定问题 A 的任意实例G = (V, E),|V|= n 为奇数。
如果|E| = 0，则图 G 不包含哈密尔顿圈，该实例为 no 实例；
如果|E| > 0，按照如下方法构造问题 B 的实例G' = (V', E'),|V'|= n' 为偶数。

任选一个顶点u ∈ V，假设 u 的邻居顶点集为{v₁, v₂, v₃, …, v_k}；

• 如果 k < 2，则图 G 不包含哈密尔顿圈，该实例为 no 实例；

• 如果 k ≥ 2，在V'中添加3个顶点v_a, v_b, v_c；添加以下边

  • u与v_a相连
  • v_a和v_b相连
  • v_b和v_c相连
  • v_c与u的所有邻居相连

• 因为|V|为奇数，则有|V'|为偶数；

图 G 中存在哈密尔顿圈当且仅当图 G’ 中存在哈密尔顿圈，证明如下：

充分性：如果图 G 中存在哈密尔顿圈 C，则 C 一定经过与顶点 u 关联的一条边，设边为(u, v₁)
则G'存在哈密尔顿圈u→v_a→v_b→v_c→v₁→其他节点→u

必要性：如果图 G' 中存在哈密尔顿圈 C'，
因为顶点 va 和 vb 都只有 2 个邻居，如果图 G’中存在哈密尔顿圈 C’，那么u→v_a→v_b→v_c 这 3 条边一定在圈 C’ 上
则C'一定是 u→v_a→v_b→v_c→u的一个邻居→其他节点→u
将C'中的 u→v_a→v_b→v_c→u的一个邻居 改成 u→u的一个邻居 ，即为G中的一个哈密尔顿圈

问题 > Longest path 最长路径问题

LONGEST-PATH. Given a directed graph G = (V, E), does there exists a simple path consisting of at least k edges?
最长路径问题：给定有向图G = (V, E)，是否存在一个简单路径包含至少k条边（k+1个顶点）

3-satisfiability reduces to longest path 三元可满足性问题 归约到 最长路径问题

Theorem. 3-SAT ≤_P LONGEST-PATH.
定理：三元可满足性问题 归约到 最长路径问题

Pf 1. Redo proof for DIR-HAM-CYCLE, ignoring back-edge from t to s.
证明1：和 三元可满足性问题 归约到 有向哈密尔顿回路问题 类似，但是忽略从终点t到起点s的回头边

Pf 2. Show HAM-CYCLE ≤_P LONGEST-PATH.
证明2：哈密尔顿回路问题 归约到 最长路径问题

★Hamilton cycle reduces to longest path 哈密尔顿回路问题 归约到 最长路径问题

给定任意哈密尔顿回路问题的实例G = (V, E)，构造最长路径问题的实例 {G’ = (V’, E’), k} 如下：

• (1) 在V中任选一顶点v, 它在G中共有h个邻居顶点u₁, u₂, u₃, …u_h.

• (2) 在V’中，顶点比V多三个，分别是v_a, v_b, v_c；E’中边比E多出以下边：

  • v_a只与v相连，
  • v_c只与v_b相连，
  • v_b与v所有邻居u相连

• (3) k为V’中顶点数减一 = |V’|-1（要求最长路径经过所有节点）

则图G中存在哈密尔顿回路当且仅当图G’中存在长度大于等于k的简单路径，证明如下：

⇒ 充分性：

• 如果图G中存在哈密尔顿圈C，则C一定经过与顶点v关联的一条边，假设为(v, u₁)
• 那么存在长度等于|V’|-1的简单路径：从v_a出发，到v，经过哈密尔顿回路回到v的一个邻居u₁，到v_b，到v_c结束

⇐ 必要性：

• 如果图G'中存在长度等于|V’|-1的简单路径（不可能大于）
• 因为顶点v_a和v_c都只有一个邻居，如果图G’中存在长度等于|V’|-1的简单路径，那么顶点v_a和v_c一定是这条路径的两个端点
• 不妨假设这条路径为v_a→v→经过所有其他节点→某个u→v_b→v_c
• 则v→经过所有其他节点→某个u→v是G中的哈密尔顿圈。

问题 > Traveling salesperson problem 旅行商问题

TSP. Given a set of n cities and a pairwise distance function d(u, v), is there a tour of length ≤ D ?
旅行商问题：给定一个城市集合以及一个表示两城市之间距离的函数d(u, v)，是否存在总长不超过D的路程，拜访每个城市恰好一次，然后回到原点

★Hamilton cycle reduces to TSP 哈密尔顿回路问题 归约到 旅行商问题

Theorem. HAM-CYCLE ≤_P TSP.
定理：哈密尔顿回路问题 归约到 旅行商问题

Pf. 证明

• Given instance G = (V, E) of HAM-CYCLE, create n cities with distance function
  对于任意给定的哈密尔顿回路问题的图G = (V, E)，构造旅行商问题的实例：创建n个城市，每个城市的距离如下函数

  $$d(u,v)=\{\begin{array}{ll}1,& \text{if }(u,v)\in E\\ 2,& \text{if }(u,v)\notin E\end{array}$$

• TSP instance has tour of length ≤ n iff G has a Hamilton cycle.
  旅行商问题有长度小于等于n的路径当且仅当存在哈密尔顿回路

Remark. TSP instance satisfies triangle inequality: d(u, w) ≤ d(u, v) + d(v, w).
注意：旅行商问题的实例满足三角形不等式：两边之和不小于第三边

Partitioning problems 划分问题 / Graph coloring 图着色问题

3-colorability 三着色问题

3-COLOR. Given an undirected graph G, can the nodes be colored red, green, and blue so that no adjacent nodes have the same color?
三着色问题：对于无向图G，是否可以使用三种颜色对顶点着色，使得任意相邻顶点颜色不同

Application: register allocation 应用：寄存器分配

Register allocation. Assign program variables to machine register so that no more than k registers are used and no two program variables that are needed at the same time are assigned to the same register.
寄存器分配问题：将程序变量分配给机器寄存器，以便使用的寄存器个数不超过k个，不要将两个同时需要的程序变量分配到同一寄存器。

Interference graph. Nodes are program variables names; edge between u and v if there exists an operation where both u and v are "live" at the same time.
干扰图：节点是程序变量的名称；如果存在u和v同时“活动”的操作，则u和v之间存在边。

Observation. [Chaitin 1982] Can solve register allocation problem iff interference graph is k-colorable.

Fact. 3-COLOR ≤_P K-REGISTER-ALLOCATION for any constant k ≥ 3.

★3-colorability reduces to k-colorability 三着色问题 归约到 k着色问题

(2021)给定k种不同的颜色，用这些颜色为无向连通图G的各顶点着色，每个顶点着一种颜色，是否有一种着色方案使G中每条边的2个顶点着不同颜色?这个问题是图的k着色判定问题。

已知图的3着色判定问题是NP完全问题，请证明图的10着色判定问题是NP完全问题。

证明：对于任意三着色问题G，构造10着色问题的实例G‘，G存在三着色当且仅当G’存在10着色

构造10着色问题：添加 k-3（7）个顶点，每个顶点与其他所有顶点相连

证明充分性：如果G可以三着色，那么在G‘中原来在G中的顶点也可以三着色，剩下的7个顶点着7重不同的颜色，即G‘可满足10着色的要求

证明必要性：如果G‘可以10着色，那么新增的7个顶点必然是7中不同的颜色，原来在G中的顶点只能再选择3种其他颜色进行着色，即G可以三着色

3-satisfiability reduces to 3-colorability 三元可满足性问题 归约到 三着色问题

Theorem. 3-SAT ≤ P 3-COLOR.
定理：三元可满足性问题 归约到 三着色问题

Pf. Given 3-SAT instance Φ, we construct an instance of 3-COLOR that is 3-colorable iff Φ is satisfiable.
证明：对于任意三元可满足性问题的实例Φ，构造一个三着色问题的实例，可三着色当且仅当Φ是可满足的

Construction. 构造

• (i) Create a graph G with a node for each literal.
• (ii) Connect each literal to its negation.
• (iii) Create 3 new nodes T, F, and B; connect them in a triangle.
• (iv) Connect each literal to B.
• (v) For each clause Cj, add a gadget of 6 nodes and 13 edges.

Pf. ⇒ Suppose graph G is 3-colorable.
・Consider assignment that sets all T literals to true.
・(iv) ensures each literal is T or F.
・(ii) ensures a literal and its negation are opposites.
・(v) ensures at least one literal in each clause is T.

Pf. ⇐ Suppose 3-SAT instance Φ is satisfiable.
・Color all true literals T.
・Color node below green node F, and node below that B.
・Color remaining middle row nodes B.
・Color remaining bottom nodes T or F as forced.

Planarity 图的平面性

Def. A graph is planar if it can be embedded in the plane in such a way that no two edges cross.
定义：如果图可以嵌入平面中，且没有两条边相交，则图是平面的。

Applications. VLSI circuit design, computer graphics, ...

Planarity testing 平面性检测

Theorem. [Hopcroft–Tarjan 1974] There exists an O(n) time algorithm to determine whether a graph is planar. (simple planar graph has at ≤ 3n edges)

Problems on planar graphs 平面图问题

Fact 0. Many graph problems can be solved faster in planar graphs.
Ex. Shortest paths, max flow, MST, matchings, …

Fact 1. Some NP-complete problems become tractable in planar graphs.
Ex. MAX-CUT, ISING, CLIQUE, GRAPH-ISOMORPHISM, 4-COLOR, ...

Fact 2. Other NP-complete problems become easier in planar graphs.
Ex. INDEPENDENT-SET, VERTEX-COVER, TSP, STEINER-TREE, ...

Planar graph 3-colorability 平面图三着色问题

PLANAR-3-COLOR. Given a planar graph, can it be colored using 3 colors so that no two adjacent nodes have the same color?
平面图三着色问题：对于无向平面图G，是否可以使用三种颜色对顶点着色，使得任意相邻顶点颜色不同

Planar map 3-colorability 平面地图三着色问题

PLANAR-MAP-3-COLOR. Given a planar map, can it be colored using 3 colors so that no two adjacent regions have the same color?

平面图三着色问题：对于平面地图，是否可以使用三种颜色对地区着色，使得任意相邻地区颜色不同

Planar graph and map 3-colorability reduce to one another 平面图三着色问题 和 平面地图三着色问题 相互归约

Theorem. PLANAR-3-COLOR ≣ P PLANAR-MAP-3-COLOR.

Pf sketch.

• Nodes correspond to regions.
• Two nodes are adjacent iff they share a nontrivial border.

Planar 3-colorability is NP-complete 平面图三着色问题是NP完全的 / 三着色问题 归约到 平面图三着色问题

Theorem. PLANAR-3-COLOR ∈ NP-complete.

Pf.

• Easy to see that PLANAR-3-COLOR ∈ NP.
• We show 3-COLOR ≤_P PLANAR-3-COLOR.
• Given 3-COLOR instance G, we construct an instance of PLANAR-3-COLOR that is 3-colorable iff G is 3-colorable.

Lemma. W is a planar graph such that:

• In any 3-coloring of W, opposite corners have the same color.
• Any assignment of colors to the corners in which opposite corners have the same color extends to a 3-coloring of W.

Pf. The only 3-colorings (modulo permutations) of W are shown below.

Construction. Given instance G of 3-COLOR, draw G in plane, letting edges cross. Form planar Gʹ by replacing each edge crossing with planar gadget W.

Lemma. G is 3-colorable iff Gʹ is 3-colorable.

• In any 3-coloring of W, a ≠ aʹ and b ≠ bʹ.
• If a ≠ aʹ and b ≠ bʹ then can extend to a 3-coloring of W.

Planar map k-colorability 平面地图k着色

Theorem. [Appel–Haken 1976] Every planar map is 4-colorable.
定理：任何平面地图都可以4着色

• Resolved century-old open problem.
• Used 50 days of computer time to deal with many special cases.
• First major theorem to be proved using computer.

Remarks.

• Appel–Haken yields O(n⁴) algorithm to 4-color of a planar map.
• Best known: O(n²) to 4-color; O(n) to 5-color.
• Determining whether 3 colors suffice is NP-complete.

Numerical problems 数值问题

Subset sum 子集合问题

SUBSET-SUM. Given n natural numbers w₁, …, w_n and an integer W, is there a subset that adds up to exactly W ?
子集合问题：给定n个自然数w₁, …, w_n和整数W，是否存在一个子集合加起来正好等于W

Ex. { 215, 215, 275, 275, 355, 355, 420, 420, 580, 580, 655, 655 }, W = 1505.
Yes. 215 + 355 + 355 + 580 = 1505.

Remark. With arithmetic problems, input integers are encoded in binary. Poly-time reduction must be polynomial in binary encoding.
注意：对于算术问题，输入整数以二进制编码。多项式归约必须在二进制编码中是多项式的。

3-satisfiability reduces to subset sum 三元可满足性问题 归约到 子集合问题

Theorem. 3-SAT ≤ P SUBSET-SUM.
定理：三元可满足性问题 归约到 子集合问题

Pf. Given an instance Φ of 3-SAT, we construct an instance of SUBSET-SUM that has solution iff Φ is satisfiable.
证明：对于任意三元可满足性问题的实例Φ，构造一个子集合问题的实例，子集合有解当且仅当Φ可满足

Construction. Given 3-SAT instance Φ with n variables and k clauses, form 2n + 2k decimal integers, each having n + k digits:
构造：对于任意给定的三元可满足性问题的实例Φ，其中有n个变量和k个子句，构造2n + 2k个十进制整数，每个整数有n + k位

• Include one digit for each variable x_i and one digit for each clause C_j.
  每个变量1位，每个子句1位
• Include two numbers for each variable x_i.
  每个变量2个整数
• Include two numbers for each clause C_j.
  每个子句2个整数
• Sum of each x_i digit is 1; sum of each C_j digit is 4.
  每个变量的那一位加起来是1，每个子句的那一位加起来是4，

Key property. No carries possible ⇒ each digit yields one equation.
关键特性：

Lemma. Φ is satisfiable iff there exists a subset that sums to W.

Pf. ⇒ Suppose 3-SAT instance Φ has satisfying assignment x*.
证明充分性：假设Φ有可满足的真值指派

• If x*_i = true, select integer in row x_i ; otherwise, select integer in row ¬ x_i.
  如果x*_i为真，选择第x_i行的整数；否则，选择第¬ x_i行的整数
• Each x_i digit sums to 1.
  每个x_i位加起来是1
• Since Φ is satisfiable, each C_j digit sums to at least 1 from x_i and ¬ x_i rows.
  因为Φ是可满足的，每个C_j位加起来至少是1
• Select dummy integers to make C_j digits sum to 4.
  选择伪整数让每个C_j位加起来是4

Pf. ⇐ Suppose there exists a subset S* that sums to W.
证明必要性：假设存在子集合S*加起来是W

• Digit x_i forces subset S* to select either row x_i or row ¬ x_i (but not both).
  x_i位会让子集合S*中必须选择且只选择第x_i行或第¬ x_i行中的一个
• If row x_i selected, assign x*_i = true ; otherwise, assign x*_i = false.
  如果第x_i行被选择了，令x*_i为真；否则令其为假
• Digit C_j forces subset S* to select at least one literal in clause.
  C_j位会让子集合S*中至少在子句中选择一个为真的字面量

★Subset sum reduces to knapsack 子集合问题 归约到 背包问题

定理：子集合问题 归约到 背包问题

证明：对于任意子集合问题的实例（每个数w_i，和W），构造背包问题的实例，子集合问题有解当且仅当背包问题有解

构造：每个物体的重量等于w_i，价值等于w_i，背包容量W，要求价值W

证明充分性：若子集合问题有解，那么选择对应的物体，可以使背包问题有解

证明必要性：若背包问题有解

Partition 划分问题

PARTITION. Given natural numbers v₁, …, v_m , can they be partitioned into two
subsets that add up to the same value ½ Σ_i v_i ?
划分问题：给定m个自然数，是否可以将其划分成两个子集，每个子集加起来刚好是所有数加起来的一半

★Subset sum reduces to partition 子集合问题 归约到 划分问题

Theorem. SUBSET-SUM ≤_P PARTITION.
定理：子集合问题 归约到 划分问题

Pf. Let W, w₁, …, w_n be an instance of SUBSET-SUM.
证明：设W, w₁, …, w_n使任意子集合问题的实例

• Create instance of PARTITION with m = n + 2 elements.
  构建一个有m = n + 2个元素的划分问题的实例
  • v₁ = w₁, v₂ = w₂, …, v_n = w_n,
    其中前n个元素相同
  • v_n+1 = 2 Σ_i w_i – W,
    第n+1个元素为2 Σ_i w_i – W
  • v_n+2 = Σ_i w_i + W
    第n+2个元素为Σ_i w_i + W
• Lemma: there exists a subset that sums to W iff there exists a partition since elements v_n+1 and v_n+2 cannot be in the same partition.
  引理：子集合问题存在解当且仅当划分问题可以分成和相等的两部分（每部分2 Σ_i w_i ），因为v_n+1和v_n+2不可能在同一个划分中

Scheduling with release times 有到达时间的活动安排问题

SCHEDULE. Given a set of n jobs with processing time t_j, release time r_j , and deadline d_j , is it possible to schedule all jobs on a single machine such that job j is processed with a contiguous slot of t_j time units in the interval [r_j, d_j]?
有到达时间的活动安排问题：给定n个活动，每个活动的处理时间是t_j，到达时间是r_j，截至时间是d_j，是否有可能在单一机器上安排这些活动，使得每个活动j在时间间隔[r_j, d_j]占用长为t_j连续一段时间

Subset sum reduces to scheduling with release times 子集合问题 归约到 有到达时间的活动安排问题

Theorem. SUBSET-SUM ≤_P SCHEDULE.
定理：子集合问题 归约到 有到达时间的活动安排问题

Pf. Given SUBSET-SUM instance w₁, …, w_n and target W, construct an instance of SCHEDULE that is feasible iff there exists a subset that sums to exactly W.
证明：给定任意子集合问题的实例，其中自然数是w₁, …, w_n，目标是W，构造一个有到达时间的活动安排问题，可以安排当且仅当存在和为W的子集合

Construction. 构造

• Create n jobs with processing time t_j = w_j, release time r_j = 0,and no deadline (d_j = 1 + Σ_j w_j ).
  创建n个活动，持续时间t_j为w_j，没有到达时间限制（一开始就到达时间），没有截止时间限制（最后才截至）
• Create job 0 with t₀ = 1, release time r₀ = W, and deadline d₀ = W + 1.
  创建一个活动0，持续时间为1，到达时间为W，截至时间为W+1（活动0必须被安排到[W, W+1]之间）
• Lemma: subset that sums to W iff there exists a feasible schedule.
  引理：子集合的和为W当且仅当存在可行的安排

★Partition reduces to k-Load-Balance 划分问题 归约到 k负载均衡问题

证明：对于任意划分问题（设所有数加起来为x），构造k负载均衡问题的实例，划分问题存在解当且仅当k负载均衡问题存在总负载不超过x/2的解

k负载均衡问题构造：划分问题每个数对应一个工作，长度等于数值；再添加k-2个工作，每个工作长度为x/2

证明充分性：如果存在划分问题解，那么将这些工作平均分成两份，分配给2台机器，剩下k-2个工作分配给k-2个机器，使得机器最大负载为x/2，为k负载均衡问题的解

证明必要性：如果k负载均衡问题存在总负载不超过x/2的解，那么必然有k-2个长度为x/2的工作分配给k-2个机器（否则总负载会超过x/2），剩下的工作只能平均分配两台机器（否则总负载会超过x/2），即划分问题存在解