Select all the steps that have to be included into the Reduction step of the Ver

Question

Select all the steps that have to be included into the Reduction step of the Vertex Cover (VC) problem. Note that incorrect choices are penalized. Select one or more: A. Claim that VC is NP-hard B. Claim the reduction from NP-hard IS problem to VC C. Set parameters for IS problem to GIs = Gvc and kis = n-kvc D. Show that IS-> VC reduction is done in O(const) time E. Set parameters for IS problem to GIs to a complement of Gvc and O F Show that VC-> IS reduction is done in O(n2) time for constructing graph complement O G. Show correctness of the reduction H. Claim that IS is in NP class

Explanation / Answer

Here we are to reduce Independent set problem to Vertex cover problem.

The correct choices are -

"A" because we know that VC problem is NP Complete . NP complete is the intersection of NP and NP hard problems.

"B" We will claim the reduction from IS to VC , to compare the NP hardness of them.

"C" We will set the parameters and if k is the independent set then n-k is the vertex cover , because if there is a edge e = (u,v) then u or v can be in k . So n-k will be the vertex cover.

"D" As I explained above we can see that they are equally hard. So reduction is done in O(const) time.

"G" We will show the correctness of the reduction.

"H" Yeah, IS problem is in NP class because it is NP Complete.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.