# Poly-time reduction: D and D Comp [duplicate]

Looking at the Independent Set problem and its complement, I want to show that IS is poly-time reducible to its complement, however I am struggling on coming up with the reduction function.

I will define its complement for further clarity, does every subset such that its size is at least $k$ in $V$ contain at least one edge between its vertices? My intuition is below.
$$f(G, k) = (G, i-k),$$ where $i = |V|$?

• It should help if you clarify what exactly you mean with the complement of IS. What problem do you mean precisely? Are you building a reduction to vertex cover, or to deciding the non-existence of an independent set, or something else?
– Juho
Mar 28, 2015 at 8:46
• IS = Independent Set Decision Problem. I am referring to Independent Set's complement. (The complement of this problem). Given a decision problem X, its complement X Complement is the collection of all instances s such that s is not in X. No I want to show that independent set is poly-time reducible to it's complement. Mar 28, 2015 at 18:23
• @Juho The complement of a decision problem is completely standard. Mar 28, 2015 at 20:10
• Are you still confused about the relationship between vertex cover and independent set? Apr 20, 2015 at 8:31

Independent set and its complement are NP-complete and co-NP-complete, respectively. If you found a polynomial-time reduction between those two problems, you'd have proven that NP$\,=\,$co-NP, resolving one of the biggest open problems in theoretical CS.