CODEWITHSUNDEEP
complexity-theorytime-complexitynp-complete
they changed my name
they changed my name

Reputation: 491

Question about NP-Completeness of the Independent Set Problem

I thought that, when proving that a problem P is NP-Complete, we were supposed to reduce a known NPC problem to P. But, looking at the solution to the Independent Set problem, it seems to not go this way.

To prove that Independent Set is NP-Complete, you take a graph G, find its inverse G', and then compute CLIQUE(G'). But, this is doing the other way around: it's taking a problem P I DON'T know if it's NPC and then reduces it to a know NPC problem.

Here's an example of the solution.

What am I missing here? Isn't this wrong, since it's doing it the other way around?

Upvotes: 0

Views: 3020

Answers (2)

BitHigher
BitHigher

Reputation: 501

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

Upvotes: 1

Eli
Eli

Reputation: 1269

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

  1. That P exists in NP.
  2. That there's a polytime reduction algorithm to reduce some NP-complete problem Q to P.

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

  1. We can verify IS trivially in polytime. Iterate vertices, ensure that each has an edge not in the candidate solution.
  2. We now need to reduce CLIQUE to IS. Given a graph G and an integer n, for CLIQUE we want to check if there's a CLIQUE of size n. Let H be the inverse of G. If you find an IS in H of size n, you have a CLIQUE of size n in G with the same vertices. We've reduced CLIQUE to IS.

If you were to reduce IS to CLIQUE, you wouldn't prove that either is in NPC unless you could reduce some other problem in NPC to IS.

Upvotes: 2

Related Questions