Given a digraph G(V, E), the Vertex Cover problem (VCover) seeks a minimum cardinality subset of vertices that together touch every edge of E.

(a) Show that the problem can be modeled in terms of decision variables xi = 1 if vertex i is in the solution and = 0 otherwise as ILP min aiVxi s.t. aiIe xi Ú 1 for all e  E xi binary for all i  V where Ie ! 5i  V6 end points of edge e.

(b) Now recall the weighted Set Covering problem (SCover) of Section 11.3 seeking a minimum total weight subcollection of subsets Sj, j  J, which together include each element of union S !  jJ Sj at least once. In terms of decision variables xj = 1 if subset j is included and = 0 otherwise, plus objective function coefficients cj, the problem can be modeled as ILP:

min ajJ cj xj s.t. a5j with iSj6xj Ú 1 for all i  S xj binary for all j  J

(c) Show that every instance of (VCover) can be viewed as an instance of (SCover). Be sure to fully detail how elements of the two formulations correspond.

(d) Problem (VCover) is known to be NPHard.

Use that fact and your result of part

(c) to show that (SCover) is NP-Hard.