NP问题练习题
8.20
In an undirected graph G=（V，E），we say D ⊆ V is a dominating set if every v∈V is either in D or adjacent to at least one member of D. In the DOMINATING SET problem，the input is a graph and a budget b, and the aim is to find a dominating set in the graph of size at most b，if one exists.Prove that this problem is NP-problem.
在无向图G =（V，E）中，如果每个v∈V在D中或与D的至少一个成员相邻，则D⊆V是支配集（dominating set）。在支配集问题中，输入是图和预算b，目标是在图形中找到一个主导的图，如果存在，最大为b。证明这个问题是NP问题。
答：可以将顶点覆盖问题归约到支配集问题。若要在图 G( V, E ) 中求得不大于 b 的一个顶点覆盖，可以先对图 G 做一个预处理：对每条边(u,v )∈E ，添加一个辅助顶点 w，及两条边(u,w )和 (v,w) ，如下图所示： 
对每条边都这样处理后得到一个新图 G’。
接下来需要证明：若原图 G 中存在不大于 b 的顶点覆盖，这个顶点覆盖也是新图 G ’ 的一个支配集；反过来，若新图 G ’ 中存在一个不大于 b 的支配集，那么对这个支配集进行一些处理后也能得到一个图 G 的不大于 b 的顶点覆盖。
下面对两个方面分别进行证明
若原图 G 中存在不大于 b 的顶点覆盖，这个顶点覆盖也是新图 G ’ 的一个支配集：
如果图G有不大于b的顶点覆盖S，对于G’中的每个顶点v，或者属于S，或者与S中的某个顶点相邻。然后假设此结论不成立，即存在v∈V，且v∉S且不与S中的任意一顶点相邻。因为图G’是连通的，所以一定存在边（u,v），且u∉S。S是G的顶点覆盖，所以（u,v）不属于E，就是说（u,v）是一条新添加的辅助边。若v为非辅助顶点，由于v的所有非辅助边均被S所覆盖，所以v一定与S中的某个顶点相邻，与假设矛盾；若v为辅助顶点，假设v对应的非辅助边为（u,w），由于（u,w）被S所覆盖，且u∉S，所以w∈S，所以存在边（v,w）使得v与S中的某个顶点相邻，与假设矛盾。所以这一部分得证。
若新图 G ’ 中存在一个不大于 b 的支配集，那么对这个支配集进行一些处理后也能得到一个图 G 的不大于 b 的顶点覆盖：
我们可以进行如下的处理：设G ’ 中有大小不大于b的支配集D，对于每条边（u,v）以及相应的辅助顶点w，若w不属于D，则不做任何处理，因为此时uv至少有一个顶点属于D，否则w,u,v都不属于D，则w不与D中任一元素相邻，与D是支配集的结论矛盾；若w∈D并且u，v∉D，那么可以在D中将w替换为u或v，若w∈D并且u∈D或者v∈D，则直接将w从D中删掉即可。所以第二个结论也是成立的。
由于已经知道顶点覆盖问题为NP完全问题，所以支配集问题也是NP完全问题。