Problem
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 E' ? E is called a feedback arc set if the removal of edges E' renders G acyclic.
FEEDBACK ARC SET (FAS): Given a directed graph G = (V, E) and a budget b, find 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 (G', b) of FAS as follows. If G = (V, E) has n vertices v1, ..., vn, then make G' = (V', E') a directed graph with 2n vertices w1, w1', ..., wn, wn', and n + 2|E|(directed) edges:
- (wi, wi') for all i = 1, 2, ..., n.
- (wi', wj) and (wj', wi) for every (vi, vj) ∈ E
(b) Show that if G contains a vertex cover of size b, then G' contains a feedback arc set of size b.
(c) Show that if G' 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 G', you may need to first 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 modified feedback arc set).
Solution
(a) 對于該問題來說, 如果存在一個(gè)解, 那么從圖G中移除若干條邊, 并驗(yàn)證其無環(huán)顯然是一個(gè)需要多項(xiàng)式時(shí)間的過程, 因此FAS屬于NP.
(b) 首先回顧一下頂點(diǎn)覆蓋的概念：
頂點(diǎn)覆蓋
對于圖G = (V, E), 對于任意點(diǎn)i ∈ V, 我們記Si 為點(diǎn)i所有相連的邊的集合.
要求從S1, ..., Sm(m = |V|)中選出b個(gè)集合, 使它們的并為E.
這b個(gè)集合就被稱為圖G的一個(gè)規(guī)模為b的頂點(diǎn)覆蓋.
根據(jù)題目提示, 設(shè)G的一個(gè)大小為b的頂點(diǎn)覆蓋為C, 對于任意頂點(diǎn)vi ∈ C, 設(shè)其在圖G' = (V', E')中相對應(yīng)的頂點(diǎn)為wi和wi'. 初始化一個(gè)空的邊集E'', 將(wi, wi')加入E''. 對C中的每個(gè)頂點(diǎn)都這樣處理后, 得到的邊集E''就是G’一個(gè)規(guī)模為b的FAS. 因?yàn)閷τ陧旤c(diǎn)wi, 去掉邊(wi, wi')后, wi就不存在任何出邊（出度為0）, 故與其相連的邊也不可能位于任何一個(gè)環(huán)中生闲；而對于頂點(diǎn)wi', 去掉邊(wi, wi')后, wi'就不存在任何入邊（入度為0）, 故與其相連的邊也不可能位于任何環(huán)中. 命題得證.
(c) 根據(jù)題目提示, 對于圖G中的任意一條邊(vi, vj), 設(shè)它的兩個(gè)頂點(diǎn)在圖G'中對應(yīng)的頂點(diǎn)為wi, wi', wj, wj', G'中對應(yīng)的邊為(wi, wj'), (wi', wj), (wj, wi'), (wj', wi). 若E''是G'的一個(gè)規(guī)模為b的FAS, 則這四條邊中, 至少有一條邊e屬于E'', 否則就會構(gòu)成環(huán)（從構(gòu)成四條邊的頂點(diǎn)就可以發(fā)現(xiàn)這個(gè)事實(shí)）. 而邊e的兩個(gè)頂點(diǎn)必然有一個(gè)屬于{wi, wj}. 設(shè)C是一個(gè)空集, 如果wi是e的頂點(diǎn), 則將vi加入C, 否則就將wj加入C. 這樣處理完所有圖G中的邊后, 得到的C即是G的一個(gè)規(guī)模不超過b的頂點(diǎn)覆蓋.
