算法导论34.5 Exercises 答案

34.5-1

先将子图同构问题定义成一种语言SUBGRAPH-ISOMORPHISM：

\[\text{SUBGRAPH-ISOMORPHISM} = \{\langle G_1, G_2\rangle : G_1\text{ is isomorphic to a subgraph of }G_2\}\]

首先证明SUBGRAPH-ISOMORPHISM属于\(\text{NP}\)。对于\(G_1=(V_1,E_1),G_2=(V_2,E_2),G_1\)同构于\(G_2\)的一个子图意味着存在\(V\subseteq V_2,E\subseteq E_2\)（其中\(E\)是从\(V\)中产生的：\(\forall u\in V,\in V,(u,v)\in E_2\)，都有\((u,v)\in E\)），以及一个双射函数\(f:V_1\rightarrow V,(u,v)\in E_1\)当且仅当\((f(u),f(v))\in E\)。对于某个证据\((V,f)\)，检验程序需要先根据集合\(V\)计算出集合\(|E|\)，再判断是否满足\(|V_1|=|V|,|E_1|=|E|\)，并且\(\forall (u,v)\in E_1\)，都有\((f(u),f(v))\in E\)即可。检验程序可以在多项式内完成检验，因此SUBGRAPH-ISOMORPHISM属于\(\text{NP}\)。

接下来证明SUBGRAPH-ISOMORPHISM是NP困难的，考虑使用团问题进行规约，即证明\(\text{CLIQUE}\le_P\text{SUBGRAPH-ISOMORPHISM}\)。对于CLIQUE问题中的任意一个实例\(\langle G,k\rangle\)，规约算法\(F\)构造出如下一个SUBGRAPH-ISOMORPHISM问题的实例\(\langle G_1,G_2\rangle\)，使得\(G\)包含一个大小为\(k\)的团，当且仅当\(G_1\)和\(G_2\)的某个子图同构。

规约过程是：\(G_1\)是\(k\)个节点的完全图，\(G_2\)是\(G\)本身。可见构造出这两个图所需要花费的时间都是多项式的。

现在证明\(G\)包含一个大小为\(k\)的团，当且仅当\(G_1\)和\(G_2\)的某个子图同构。

充分性：如果\(G(G_2)\)包含一个大小为\(k\)的团，那么取出这个团所代表的子图，它将是一个大小为\(k\)的完全图，因此这个子图明显和\(G_1\)同构。

必要性：如果\(G_1\)和\(G_2\)中的某个子图同构，由于\(G_1\)是一个具有\(k\)个节点的完全图，那么\(G(G_2)\)也将包含一个边和节点一一对应的子图。因此它必定是\(G\)中一个大小为\(k\)的团。

因此\(\text{CLIQUE}\le_P\text{SUBGRAPH-ISOMORPHISM}\)。由于CLIQUE是NP完全的，那么SUBGRAPH-ISOMORPHISM是NP困难的，也是NP完全的，原结论成立。

34.5-2

先将0-1整数规划问题定义成一种语言0-1-INTEGER-PROGRAMMING：

\[\begin{aligned} \text{0-1-INTEGER-PROGRAMMING}=\{\langle A,b\rangle:&A\text{ is a }m\times n\text{ matrix},\\ &b\text{ is a }m\text{-vector},\text{ and}\\ &\text{there exists a }n\text{-0-1-vector }x\text{ such that }Ax\le b \} \end{aligned}\]

首先证明0-1整数规划问题0-1-INTEGER-PROGRAMMING属于\(\text{NP}\)。对于一组输入\(\langle A,b\rangle\)和一个证书：\(n\)维向量\(x\)，检验算法只需要先判断\(x\)是否为一个\(0\text{-}1\)向量，然后再计算\(b'=Ax\)，并检验是否满足\(b'\le b\)即可。这个检验过程可以在多项式时间内完成，因此0-1-INTEGER-PROGRAMMING属于\(\text{NP}\)。

接下来证明0-1-INTEGER-PROGRAMMING是NP困难的，考虑使用3-CNF可满足行性问题进行规约，即证明\(\text{3-CNF-SAT}\le_P\text{0-1-INTEGER-PROGRAMMING}\)。给定变量\(x_1,x_2,\dots,x_n\)的一个3-CNF公式\(\phi\)，它由子句\(\phi_1,\phi_2,\dots,\phi_k\)构成。规约算法\(F\)将构造0-1-INTEGER-PROGRAMMING问题的一个实例\(\langle A,b\rangle\)使得\(\phi\)是可满足的，当且仅当存在0-1向量\(x\)，使得\(Ax\le b\)。

规约的过程如下：

• 对于每一个变量\(x_i\)，在0-1整数规划中都用\(2\)个未知数\(y_i,\neg y_i\)来表示，\(x_i\)对应了\(y_i\)；\(\neg x_i\)对应着\(\neg y_i\)。那么列出两条不等式：\(y_i+\neg y_i\le 1,y_i+\neg y_i\ge 1\)，这是为了保证\(y_i+\neg y_i=1\)成立。

• 对于每一个子句\(\phi_i=z_{i,1}\lor z_{i,2}\lor z_{i,3}\)，将每个文字转换成对应的未知数后（设为\(y_{i,1}, y_{i,2}, y_{i,3}\)），列出不等式\(y_{i,1}+y_{i,2}+y_{i,3}\ge 1\)。这意味着，每个公式中，至少有一个布尔变量的取值为\(1\)。

接下来只需要将带有大于等于号的公式两侧取负，那么就转换成了都是小于等于号的公式。

可见，规约算法构造出了\(2n+k\)条不等式，这些不等式的未知变量个数为\(2n\)。因此，矩阵\(A\)的大小为\((2n+k)\times 2n\)。可见，规约算法\(F\)能够将矩阵\(A\)和向量\(b\)在多项式时间内能构造出来。

现在证明\(\phi\)是可满足的，当且仅当存在0-1向量\(x\)，使得\(Ax\le b\)。

充分性：首先假设\(\phi\)存在着一组可满足性赋值\(x_1,x_2,\dots,x_n\)，那么令\(y_i=x_i,\neg y_i=\neg x_i\)。在这个赋值下，\(y_i+\neg y_{i}=1\)必定成立。由于每个子句\(\phi_i\)都是为\(1\)，因此必定存在某个文字\(z_{i,j}\)所对应的未知变量\(x_{i,j}\)的赋值为\(1\)，从而使得下面\(k\)个不等式中大于等于\(1\)成立。因此如果\(\phi\)是可满足的，可以对对应的0-1整数规划问题\(\langle A,b\rangle\)实例找到一组解。

必要性：首先假设这组0-1整数规划问题实例\(\langle A,b\rangle\)存在一组解。在这组解中，构造一组\(\phi\)上变量的赋值\(x_i=y_i\)。由于\(\forall i\in[1,k],y_{i,1}+y_{i,2}+y_{i,3}\ge 1\)均成立，这意味着所有子句\(\phi_i\)中，都必有其中一个变量为\(1\)。因此\(\phi\)是可满足的。

因此\(\text{3-CNF-SAT}\le_P\text{0-1-INTEGER-PROGRAMMING}\)。由于3-CNF-SAT是NP完全的，那么0-1-INTEGER-PROGRAMMING是NP困难的，也是NP完全的，原结论成立。

34.5-3

先将整数规划问题定义成一种语言INTEGER-LINEAR-PROGRAMMING：

\[\begin{aligned} \text{INTEGER-LINEAR-PROGRAMMING}=\{\langle A,b\rangle:&A\text{ is a }m\times n\text{ matrix},\\ &b\text{ is a }m\text{-vector},\text{ and}\\ &\text{there exists a }n\text{-vector }x\text{ such that }Ax\le b \} \end{aligned}\]

首先证明整数规划问题INTEGER-LINEAR-PROGRAMMING属于\(\text{NP}\)。对于一组输入\(\langle A,b\rangle\)和一个证书：\(n\)维向量\(x\)，检验算法只需要先判断\(x\)是否为一个整数向量，然后再计算\(b'=Ax\)，并检验是否满足\(b'\le b\)即可。这个检验过程可以在多项式时间内完成，因此INTEGER-LINEAR-PROGRAMMING属于\(\text{NP}\)。

不过，题目34.5-2所规约而来的实例\(\langle A,b\rangle\)恰好也是一个整数规划问题。因此，按照和题目34.5-2完全一样的论证过程，可以证明INTEGER-LINEAR-PROGRAMMING也是NP困难的，从而得知它是NP安全的，原结论成立。

34.5-4

如果目标值\(t\)可以表示成一元形式，那么可以构造出和0-1背包问题类似的动态规划算法进行解决（可以利用题目15.2-2所提到的算法）。将每一个数\(x_i\)视为物品的种类，将目标\(t\)视为背包的总重量，那么可以判断背包是否能否被恰好装满即可。

算法0-1-KNAPSACK-PROBLEM'给出了整个过程，它是0-1-KNAPSACK-PROBLEM的改造，用于解决这个问题：

0-1-KNAPSACK-PROBLEM(x, n, t)
  let f[0 : t] be a new array by 0
  f[0] = 1
  for i = 1 to n
    for j = t down to x[i]
      if f[j - w] == 1
        f[j] = 1
  return f[t]

可见，这个过程的时间复杂度为\(O(nt)\)。由于\(t\)是一元编码的，因此其输入规模取决于\(t\)值本身的大小。因此这个算法是一个多项式算法。

34.5-5

先将集合划分问题定义成一种语言SET-PARTITION：

\[\text{SET-PARTITION} = \left\{\langle S\rangle : \text{there exists a set }A\subseteq S\text{ such that }\sum_{x\in A} x=\sum_{x\in\overline{A}}x\right\}\]

首先证明SET-PARTITION属于\(\text{NP}\)。对于\(S\)和它的一个非空子集\(A\)，检验程序只需要判断\(\displaystyle{2\sum_{x\in A}x=\sum_{x\in S}x}\)是否满足即可，它可以在多项式时间内运行，因此SET-PARTITION属于\(\text{NP}\)。

接下来证明SET-PARTITION是NP困难的，考虑使用子集和问题进行规约，即证明\(\text{SUBSET-SUM}\le_P\text{SET-PARTITION}\)。对于SUBSET-SUM问题中的任意一个实例\(\langle S,t\rangle\)，规约算法\(F\)构造出如下一个SET-PARTITION问题的实例\(\langle S'\rangle\)，使得\(S\)包含一个和为\(t\)的子集，当且仅当\(S'\)能够划分成两个和值相等的子集。

规约过程是：计算出\(\displaystyle{s=\sum_{x\in S}x}\)后，令\(S'=S\cup\{2s-t,s+t\}\)，现在集合\(S'\)的所有数之和为\(4s\)。

现在证明\(S\)包含一个和为\(t\)的子集，当且仅当\(S'\)能够划分成两个和值相等的子集。

充分性：如果\(S\)包含一个和为\(t\)的子集\(T\)，那么令\(T'=T\cup\{2s-t\}\)，可见\(T'\subseteq S'\)，并且\(T'\)的和恰好是\(S'\)的一半，故\(T'\)为\(\langle S'\rangle\)的一个证据。

必要性：如果\(S'\)可以划分为两个相等的子集\(T'\)和\(S'-T'\)。那么考虑\(2s-t,s+t\)这两个数所属于的子集。由于\((2s-t)+(s+t)=3s>\dfrac{1}{2}\cdot 4s\)，因此\(2s-t\)和\(s+t\)在这种情况下，必定会划分在两个不同的子集。不失一般性，假设\(2s-t\)在\(T'\)所处的子集，那么令\(T=T'-\{2s-t\}\)，可以发现\(T\subseteq S\)，并且\(T\)的元素之和为\(t\)，故\(T\)为\(\langle S,t\rangle\)的一个证据。

因此\(\text{SUBSET-SUM}\le_P\text{SET-PARTITION}\)。由于SUBSET-SUM是NP完全的，那么SET-PARTITION是NP困难的，也是NP完全的，原结论成立。

34.5-6

先将哈密顿路径问题定义成一种语言HAM-PATH:

\[\text{HAM-PATH} = \{\langle G\rangle : \text{there exists a hamiltonian path in }G\}\]

首先证明HAM-PATH属于\(\text{NP}\)。对于图\(G=(V,E)\)和它的一个顶点序列\(P\)，检验程序只需要判断\(P\)是否为一条简单路径，并且经过了\(V\)中的所有顶点即可。它可以在多项式时间内运行，因此HAM-PATH属于\(\text{NP}\)。

接下来证明HAM-PATH是NP困难的，考虑使用哈密顿回路问题进行规约，即证明\(\text{HAM-CYCLE}\le_P\text{HAM-PATH}\)。对于HAM-PATH问题中的任意一个实例\(\langle G\rangle\)，规约算法\(F\)构造出如下一个HAM-PATH问题的实例\(\langle G'\rangle\)，使得\(G=(V,E)\)包含一条哈密顿回路，当且仅当\(G'=(V',E')\)包含一条哈密顿路径。

规约过程是：选择\(V\)中的一个顶点\(u\)，那么构造\(V'=V\cup \{s,t,u'\},E=E\cup\{(s,u),(t,u')\}\cup\{(u',w):(u,w)\in E\}\)。也就是说，\(u'\)是\(u\)的一个复制点，其所有邻居都和\(u\)相同。可见\(|E'|\le 2|E|+2\)，因此图\(G'\)可以在多项式时间内构造出来。

现在证明\(G=(V,E)\)包含一条哈密顿回路，当且仅当\(G'=(V',E')\)包含一条哈密顿路径。

充分性：如果\(G\)包含了一条哈密顿回路\(C=(u,v_1,v_2,\dots,v_{n-1},u)\)，那么考虑将\(C\)删去边\((v_{n-1},u)\)，并加上边\((v_{n-1},u'),(u',t),(s,u)\)，得到路径\(P\)，那么路径\(P\)将是一条经过\(G'\)中所有顶点的简单路径，因此\(P\)是\(G'\)的一条哈密顿路径。

必要性：假设\(G'\)包含了一条哈密顿路径\(P\)。由于图\(G'\)有且仅有两个顶点\(s,t\)的度数为\(1\)，因此\(P\)两端的节点必定是\(s,t\)。由于\(s\)和\(u\)相连，\(t\)和\(u'\)相连，因此\(P'\)为这个形式：\((s,u,v_1',v_2',\dots,v_{n-1}',u',t)\)。对\(P'\)删去边\((s,u),(v_{n-1}',u'),(u',t)\)并加上边\((v_{n-1}',u)\)，得到回路\(C\)，那么回路\(C\)将是一条经过\(G\)中所有顶点的简单回路，因此\(C\)是\(G\)的一条哈密顿回路。

因此\(\text{HAM-CYCLE}\le_P\text{HAM-PATH}\)。由于HAM-CYCLE是NP完全的，那么HAM-PATH是NP困难的，也是NP完全的，原结论成立。

34.5-7

这个问题的判定性版本为：给定一个图\(G\)和一个正整数\(k\)，判断图\(G\)是否存在一个长度至少为\(k\)的简单回路？

题目34.1-2将最长简单回路问题定义成一种语言CYCLE:

\[\begin{aligned} \text{CYCLE}=\{\langle G, k\rangle:&G = (V, E)\text{ is an undirected graph, }\\ &k \ge 0\text{ is an integer, and}\\ &G\text{ contains a cycle at least }k\text{ edges}\} \end{aligned}\]

首先证明CYCLE属于\(\text{NP}\)。对于问题的一个实例\(\langle G,k\rangle,G=(V,E)\)和它的一个顶点序列\(P\)，检验程序只需要判断\(P\)是否为一条首尾相接的简单回路，并且长度至少为\(k\)即可。它可以在多项式时间内运行，因此CYCLE属于\(\text{NP}\)。

接下来证明CYCLE是NP困难的，考虑使用哈密顿回路问题进行规约，即证明\(\text{HAM-CYCLE}\le_P\text{CYCLE}\)。对于HAM-CYCLE问题中的任意一个实例\(\langle G\rangle\)，规约算法\(F\)构造出如下一个CYCLE问题的实例\(\langle G,k\rangle\)，使得\(G\)包含一条哈密顿回路，当且仅当\(\langle G,k\rangle\)包含一条长度至少为\(k\)的简单回路。

规约过程是：如果HAM-CYCLE问题中的图为\(G=(V,E)\)，那么令CYCLE问题某个实例\(\langle G,k\rangle\)中的\(k=|V|\)即可。可见，只需要对HAM-CYCLE问题中的图再额外添加一个数\(|V|\)，\(F\)就完成工作，因此\(F\)是多项式算法。

现在证明\(G=(V,E)\)包含一条哈密顿回路，当且仅当\(\langle G,|V|\rangle\)包含一条长度至少为\(|V|\)的简单回路。这是显而易见的，因为一条哈密顿回路，恰好正是一条长度为\(|V|\)的简单回路，反之亦然。

因此\(\text{HAM-CYCLE}\le_P\text{CYCLE}\)。由于HAM-CYCLE是NP完全的，那么CYCLE是NP困难的，也是NP完全的，原结论成立。

34.5-8

先将半3-CNF可满足性问题定义成一种语言HALF-3-CNF-SAT：这门语言和3-CNF-SAT定义类似，只是恰有一半的子句的值为\(1\)，一半的子句的值为\(0\)。

首先证明HALF-3-CNF-SAT属于\(\text{NP}\)。对于一条输入公式\(\phi\)和一组输入赋值\(x\)，检验程序需要判断\(\phi\)是否是\(3\)合取范式，然后再为\(\phi\)的每个子句赋值，并计算出每个子句\(\phi_i\)的输出值。统计这些子句输出值为\(0\)的个数\(c_0\)和为\(1\)的个数\(c_1\)，并判断是否有\(c_0=c_1\)。该检验程序多项式可以在多项式时间内完成，因此HALF-3-CNF-SAT属于\(\text{NP}\)。

接下来证明HALF-3-CNF-SAT是NP困难的，考虑使用3-CNF可满足行性问题进行规约，即证明\(\text{3-CNF-SAT}\le_P\text{HALF-3-CNF-SAT}\)。对于3-CNF-SAT问题中的任意一个实例\(\langle \phi\rangle\)，规约算法\(F\)构造出如下一个HALF-3-CNF-SAT问题的实例\(\langle \phi'\rangle\)，使得\(\phi\)是可满足的，当且仅当\(\phi'\)是半可满足的。

规约过程是：对于一个\(n\)个变量，\(m\)个子句公式\(\phi\)添加\(m\)个恒真子句\(x\lor x\lor\neg x\)，以及\(2m\)个取决于\(x\)的\(x\)子句\(x\lor x\lor x\)，那么就构造出了一个具有\(4m\)个子句的公式\(\phi'\)。由于\(\phi'\)的公式长度仅为\(\phi\)的\(4\)倍，因此\(F\)是多项式算法。

现在证明\(\phi\)是可满足的，当且仅当\(\phi'\)是半可满足的。

充分性：如果\(\phi\)是可满足的，那么将同样对应的变量赋值到\(\phi'\)中，并且取\(x=0\)，那么原来的\(m\)个子句和\(m\)个恒真子句均为\(1\)，其余的\(2m\)个\(x\)子句的值为\(0\)。因此这个赋值说明公式\(\phi'\)是半3-CNF可满足的。

必要性：假设\(\phi'\)是半3-CNF可满足的，并存在一组解。由于\(\phi'\)中有\(m\)个恒真子句，如果\(x=1\)，那么\(\phi'\)中有至少\(3m\)个子句的值为\(1\)，这是不可能的，因此只能有\(x=0\)。这说明属于\(\phi\)的\(m\)个子句的值必定为\(1\)。取出这些变量的赋值赋给\(\phi\)，那么\(\phi\)的值必定为\(1\)，这说明公式\(\phi\)是3-CNF可满足的。

因此\(\text{3-CNF-SAT}\le_P\text{HALF-3-CNF-SAT}\)。由于3-CNF-SAT是NP完全的，那么HALF-3-CNF-SAT是NP困难的，也是NP完全的，原结论成立。

34.5-9

在对定理34.13证明的时候，有一个步骤是将以下边集添加到\(E'\)中：

\[\{(s_j, [u, u^{(1)}, 1]) : u \in V \text{ and } 1 \le j \le k\}\cup \{(s_j, [u, u^{(\text{degree}(u))}, 6]) : u \in V\text{ and }1 \le j \le k\}\]

对于某个孤立节点\(w\)，并没有边与它相关联，因此并不存在节点\([w,w^{(1)},1]\)和\([w,w^{(0)},6]\)，但是又有\(w\in V\)，最终这种情况下证明会产生错误。