8.12 The k-spanning tree problem is the following.
Input: An undirected graph G = (V,E)
Output: A spanning tree of G in which each node has degree ≤ k, if such a tree exists.
Show that for any k ≥ 2:
(a) k-spanning tree is search problem.
(b) k-spanning tree is NP-complete.(HINT:Start with k=2 and consider the relation between this problem and RUDRATA PATH.)
(k-生成树问题是这样的：
输入：无向图G = (V,E)
输出：G的一个生成树，其中所有的节点度数不超过k-----如果该树存在的话。
请证明对任意的k，k≥2：
(a) k-生成树问题是一个搜索问题
(b) k-生成树是NP-完全问题。(提示：由k=2 开始，考虑该问题与RUDRATA路径问题的关联))
解：
(a)k-生成树是指给定一个无向图，找到一个生成树，其中每个节点的度数不超过k。验证任意给定的正解S是否是k生成树的过程，只需要用图搜索算法对S进行搜索，假设通过搜索可以知道S中所有顶点，不包含环，且每个点的度数不超过K，那么S就是K的生成树。同时我们知道图的搜索算法可以在多项式时间内解决，因此k-生成树问题是一个搜索问题，同时也证明它是一个NP问题。
(b)由(a)我们可以知道K-生成树一个完全问题，而证明是NP-完全问题只需要找到一个NP-完全问题规约到K-生成树问题。我们可以将RUDRATA路径问题规约到K-生成树问题。若K=2，此时的2-SPANNING TREE实际上就是一条RUDRATA路径。当K＞2的时候，只要找到一课2-SPNNING TREE就可以找到k-SPANNING TREE.因此对于每个图通过搜索RUDRATA路径问题就可以通过寻找K-SPANNING TREE来解决。也就是说RUARATA路径问题可以规约为k-SPANNING TREE问题。综上k-生成树问题是NP-完全问题。
8.14 Prove that the following problem is NP-complete: given an undirected graph G = (V, E) and an integer k, return a clique of size k as weill as an independent set of size k, provided both exist.
( 证明如下问题是NP-完全的：给定一个无向图G=(V, E)和整数k，求G中一个规模为k的集以及一个规模为k 的独立集。假定他们都是存在的。)
解：可以将最大独立集问题规约到此问题。比如若要求任意图G(V, E)中大小为d的独立集，可以令G1 = G(V, E)，再令G2(V,∅)的顶点集与G相同，但是边集为空，也即是各个定点相互独立。于是G1与G2存在着大小为d的公共子图，当且仅当图G存在着大小为d的独立集。
