Cheap and Secure Web Hosting Provider : See Now

[Answers] NP-Complete Proof of k sized common set

, , No Comments
Problem Detail: 

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.

Asked By : hardstudent

Answered By : hardstudent

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$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback