In task scheduling, it is common to use a graph representation with a node for each task a...

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, w′1,..., wn, w′n, and n + 2|E | (directed) edges:

• (wi, w′i) for all i =1,2,...,n.

• (w′i, wj) and (w′j, 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.)