2
$\begingroup$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that the most straight forward reduction? Is it can also be shown directly from Clique problem?

$\endgroup$
1
$\begingroup$

Clique is the decision version of Maximum Clique, which is an optimization problem:

  • Clique: Given a graph $G$ and an integer $k$, decide whether there is a $k$-clique in $G$.
  • Maximum Clique: Given a graph $G$, find the maximum size of a clique.

Let me mention that these names are not standard. Other people might use Clique or Maximum Clique to refer to slightly different problems. Optimization problems and their decision versions are often confused in the literature, since usually it is clear from context which of the two is referred to.

There is a canonical way to convert an optimization problem to a decision problem, demonstrated above. This conversion ensures, in most circumstances, that the decision version is in NP.

We say that an optimization problem is NP-hard if its decision version is. To show that Maximum Independent Set is hard, you really need to show (by definition) that Independent Set is hard; and this you can do by reduction from Clique (not Maximum Clique).

Also, Clique and Independent Set are really the same problem — you get one from the other by complementing the graph.

Finally, let me stress that Independent Set is NP-complete, but it is not known to be in coNP or to be coNP-hard; indeed, it is conjectured not to be in coNP and not to be coNP-hard (otherwise NP=coNP).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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