I know that 3-SAT is polynomially reducable to INDEPENDENT-SET problem. Now is an INDEPENDENT-SET problem polynomially reducable to 3-SAT problem ? Thus are these problems polynomially equivalent?
I think it is, as every instance of INDEPENDENT-SET problem according to me can be represented in 3-SAT ( in some cases after adding a few extra edges ). However I am not clear about this understanding of mine.
Please help me our here.
Yes, the independent set problem can be reduced to 3SAT in polynomial time. The decision problem "given a graph G and number k, is there an independent set in G of size at least k?" is in NP (do you see why?). Since 3SAT is NP-complete, all problems in NP are polynomial-time reducible to it, and therefore the independent set problem is reducible to it.
Hope this helps!