0
$\begingroup$

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|$?

$\endgroup$
4
  • 1
    $\begingroup$ 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? $\endgroup$
    – Juho
    Mar 28, 2015 at 8:46
  • $\begingroup$ 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. $\endgroup$ Mar 28, 2015 at 18:23
  • $\begingroup$ @Juho The complement of a decision problem is completely standard. $\endgroup$ Mar 28, 2015 at 20:10
  • $\begingroup$ Are you still confused about the relationship between vertex cover and independent set? $\endgroup$
    – Pål GD
    Apr 20, 2015 at 8:31

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Ah okay! What if on top of this, Independent set and its complement are NP-complete and co-NP-complete, respectively. If you found a polynomial-time reduction between those two problems, and Independent Set is NP-complete which it is, what would possibly be the strongest claim to be made? would it be the same? $\endgroup$ Mar 28, 2015 at 21:26
  • $\begingroup$ What do you mean "What if on top of this, [IS] and its complement are NP-complete and co-NP-complete, respectively"? That's not a what-if: it's a statement of fact. And it's not "on top of" what I said: it's exactly what I said. $\endgroup$ Mar 28, 2015 at 21:31
  • $\begingroup$ My apologies didn't read it carefully. Thanks. $\endgroup$ Mar 28, 2015 at 21:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.