NP问题证明 8.22

算法题目 ：Algorithms Chapter 8  No22

算法题目描述： 

8.22. In task scheduling, it is common to use a graph representation with a node for each task and a directed edge from task i to task j if i is a precondition for j. This directed graph depicts the precedence constraints in the scheduling problem. Clearly, a schedule is possible if and only if the graph is acyclic; if it isn't, we'd like to identify the smallest number of constraints that must be dropped so as to make it acyclic. Given a directed graph G = (V;E), a subset E0 E is called a feedback arc set if the removal of edges E0 renders G acyclic. FEEDBACK ARC SET (FAS): Given a directed graph G = (V;E) and a budget b, nd a feedback arc set of b edges, if one exists. (a) Show that FAS is in NP. FAS can be shown to be NP-complete by a reduction from VERTEX COVER. Given an instance (G; b) of VERTEX COVER, where G is an undirected graph and we want a vertex cover of size b, we construct a instance (G0; b) of FAS as follows. If G = (V;E) has n vertices v1; : : : ; vn, then make G0 = (V 0;E0) a directed graph with 2n vertices w1;w01; : : : ;wn;w0n , and n + 2jEj (directed) edges:(wi ;w0i) for all i = 1; 2; : : : ; n. (w0i;wj ) and (w0j;wi) for every (vi; vj ) 2 E. (b) Show that if G contains a vertex cover of size b, then G0 contains a feedback arc set of size b. (c) Show that if G0 contains a feedback arc set of size b, then G contains a vertex cover of size (at most) b. (Hint: given a feedback arc set of size b in G0, you may need to rst modify it slightly to obtain another one which is of a more convenient form, but is of the same size or smaller. Then, argue that G must contain a vertex cover of the same size as the modied feedback arc set.)

证明：

a) 显然 FAS 是可在多项式时间内验证的，因此属于NP。 b) 设G 的一个大小为b 的顶点覆盖为C ，对于任意顶点iv ∈C ，设其在G'中相对 应的顶点为i w 和' i w ，则将边( , ') i i w w 添加到E '。对C中的每个顶点都这样处 理后，所得到的边集E '即是G'的一个大小为b 的 feedback arc set。因为对于顶 点i w 和' i w ，当去掉边( , ') i i w w 后，所有与i w 相连的边都不可能位于任何一个 环中，因为i w 不存在出边，同样，所有与' i w 相连的边也不可能位于任何一个 环中，因为' i w 不存在入边。 c) 对于G 中的任意一条边( , ) i j v v ，设其在G'中相对应的顶点为 i w 、' i w 、j w 、 ' j w ，相对应的边为( , ') i i w w 、( , ') j j w w 、( ', ) i j w w 、( ', ) j i w w 。若E '是G'的 一个大小为b 的 feedback arc set，显然，在这四条边中至少有一条边e属于E '， 否则就会形成环，而边e必然有个端点属于{ , } i j w w 。若i w 是e 的端点，则将i v 加入到C ，否则将j v 加入到C 。容易看出，在经过上述处理后，C 即是G 的一 个大小不超过b 的顶点覆盖。