Let E be a set of elements. We say that a subset AE punches another subset BE if their intersection is non-empty, i.e., if AB=. We say that A is a punching set for a set S2^E of subsets of E if A punches every set in S, i.e., if AS = for every SS. Here, the notation 2^E denotes the set of all subsets of E, i.e.: 2^E={EEE}.

Consider the following (computational) problem:

PUNCHING SET: INPUT: A set E of elements, a set S2^E of subsets of E with /S, and an integer k.

QUESTION: Does S have a punching set of size at most k, i.e., is there a set PE with |P| k such that PS= for every S S?

Example: Let E={1,2,3,4,5} and let S consists of the sets S1={1,2,3}, S2={4,5}, and S3={3,4}. Then: the sets {1} and {1,2} punch only the set S1, the set {3} punches the sets S1 and S3 (but not the set S2), the set {4} punches the sets S2 and S3 (but not the set S1), the set {5} punches only the set S2, the set {3,4} is a punching set for the instance of size 2, and there is no punching set of size 1

ANSWER ONLY PART A AND B

A) Show that the punching set problem is in NP?

B)Show that the Punching Set problem is NP-hard. (use a polynomial-time reduction from Vertex Cover).