Geek Answers Handbook

The question of the completeness of an NP-problem of an independent set

I thought that in proving that the P problem is NP-Complete, we should have reduced the known NPC problem to P. But, looking at the solution to the Independent Set problem, it seems like this is not the case.

To prove that the independent set NP-Complete, you take the graph G, find its inverse G ', and then calculate CLIQUE (G'). But, this is done the other way around: it accepts the problem P I DO NOT know if it is an NPC, and then reduces it to a known NPC problem.

Here is an example of a solution.

What am I missing here? Isn't that because he does it the other way around?

0
source share
2 answers

To prove that P is NP-complete, we need to show two things:

  • That P exists in NP.
  • That there is a time reduction algorithm for reducing the NP-complete problem Q to P.

If we know that CLIQUE is in NPCs, then we can easily prove that IS is in NPCs.

  • We can check IS trivially in polytime. Iterating over vertices, make sure everyone has an edge that is not part of the candidate’s solution.
  • Now we need to reduce CLIQUE to IS. Given a graph G and an integer n , for CLIQUE we want to check if there is a CLIQUE of size n . Let H be the inverse of G If you find IS in H size n , you have a CLIQUE of size n in G with the same vertices. We reduced CLIQUE to IS.

If you need to reduce the IS value to CLIQUE, you will not prove that it is in the NPC, unless you can reduce some other problems in the NPC to IS.

+2
source

I think this page can help you http://mlnotes.com/2013/04/29/npc.html

+1
source

More articles:


All Articles