Input: A set $U= \{w_1, w_2, \ldots, w_n\}$, subsets $S_1, S_2, \ldots, S_m$ of $U$ and integer $k$.
Question: Is there a subset with $k$ elements of $U$ which intersects of every $S_i$?

Which reduction should i use to prove that this is np-complete ?

Hint: Reduction from vertex cover.

  • 1
    $\begingroup$ What problems do you know that might work? Do you know anything that sounds similar? There are a number of possibilities here (your problem is a very well known one). $\endgroup$ – Luke Mathieson Jan 23 '15 at 0:34
  • $\begingroup$ It reminds a little bit of set cover. I tried to turn the problem into a graph but i couldn't think anything past this stage.(Man, i am sorry. I didnt know that this is well known problem. I studying on my own and i having problem with these kind of problems. May be i am stupid or i don't have sufficient knowlegde. I would i appreciate if you could suggest ways to gain experience). $\endgroup$ – hardstudent Jan 23 '15 at 2:41
  • 1
    $\begingroup$ no need for apologies, the comment that it is well known was just a gentle hint that the answer is out there. You are right to think of set cover - it's a very closely related problem. In fact there is a reduction from Set Cover, and turning Set Cover and this problem into the right sort of graph might help you see it (think bipartite). As for gaining experience, you're on the right track, it just takes practice and time, and it's not always easy. $\endgroup$ – Luke Mathieson Jan 23 '15 at 3:20
  • $\begingroup$ Thanks, you helped me a lot. Would you mind sharing any helpful resources ? I really want to improve. $\endgroup$ – hardstudent Jan 23 '15 at 9:46
  • $\begingroup$ Reopened, because the question is answerable. Please do post an answer — but note that “reduction from vertex cover” isn't an answer. An answer would explain how and why that helps. $\endgroup$ – Gilles Jan 28 '15 at 23:10

We will reduce vertex cover to our problem.

Problem: Vertex Cover
Input: Graph $G(V,E)$ and integer k
Question: Is there a subset $V'\subseteq$ V : $|V|\leq k$ which contains at least one vertex of each edge in $E$.

Reduction: For every $e_i$ edge of $G$, we build a set $S_i=\left \{u_i,v_i \right \}$ where $u_i,v_i$ are the incident vertices of $e_i$. If there is a set with size k which intersects with every $S_i$, it means that this set contains at least one vertex of each edge in $G$. In other words its a vertex cover with size k.

Because the reduction can be done in polynomial time and vertex cover $\in NP-Complete$, we can conclude that k sized common set is $NP-Complete$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.