Question

Let E be a set of elements. We say that a subset A⊆E punches another subset B⊆E if their intersection is non-empty, i.e., if A∩B=∅. We say that A is a punching set for a set S⊆2^E of subsets of E if A punches every set in S, i.e., if A∩S =∅ for every S∈S. Here, the notation 2^E denotes the set of all subsets of E, i.e.: 2^E={E′∣E′⊆E}.

Consider the following (computational) problem:
PUNCHING SET: INPUT: A set E of elements, a set S⊆2^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 P⊆E with |P| ≤ k such that P∩S=∅ 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).

Answer 1

A) To show that the punching set problem is in NP, we need to demonstrate that there is a polynomial-time verifier for a proof of yes instances. For every input, the verifier performs the following steps:

1.Take the input set E, S, and k.

2.Choose any subset P of E with |P|≤k.

3.Check if P punches every set in S.

To check if P punches every set in S, we can go through each set one by one and check if the intersection is empty. Since the number of sets in S is polynomial in the size of the input, and the size of E is fixed, this step can be performed in polynomial time. Therefore, the punching set problem is indeed in NP.

B) To show that the punching set problem is NP-hard, we will reduce the well-known NP-hard problem Vertex Cover to it. Given an undirected graph G=(V,E) and an integer k, we will construct a punching set problem instance with E and S of polynomial size.

The set of elements E will consist of the vertices of G and k additional elements, where each element corresponds to an edge of G. For each edge (v,w) in G, we will add the element corresponding to E to S and to the punching set. The set S will thus consist of the subsets of E corresponding to the vertex covers of G. The goal is to find a punching set P of E of size at most k such that P punches every subset of S.

To see that such a P exists if and only if G has a vertex cover of size at most k, observe that P punches a subset of S corresponding to a vertex cover of G if and only if P contains no element corresponding to an edge not in the vertex cover. Therefore, a punching set of size at most k exists if and only if G has a vertex cover of size at most k. Thus the punching set problem is NP-hard