# Is Maximum Independent Set in coNP

I need to determine whether the following problem $X$ is in coNP:

Given a graph $G=(V,E)$ and a positive integer $s\leq|V|$, is there an independent set that is the largest for $G$ of size at least $s$?

My solution for this was that in fact the above problem is in coNP because we can provide an NP solution for $\overline{X}$ which has the following certificate and certifier.

The certificate being a set of vertices $V'$.

The certifier does two things:

1. Checks if $V' \subseteq V$.
2. Checks for each pair of vertices in $V'$ if there exists no edge.
3. Checks if $|V'|<s$.

The certifier computes this in $O(V+E)+O(1)$.

Is this the right way to show if X is in coNP?

Edit: The independent set is required to be the largest possible for graph $G$.

• You have provided a certificate for yes-instances. This shows that your problem is in $NP$. To show that a problem is in coNP, you have to find a certificate for no-instances; you have to find a disproof. For some problems, such as this formula $\phi$ is not satisfiable, a disproof is simple: simply give a satisfying assignment, and we know that the proposition is false. In any case, have a look at the Wikipedia article – Lieuwe Vinkhuijzen Dec 2 '16 at 12:21
• @LieuweVinkhuijzen According to en.wikipedia.org/wiki/Co-NP, it says the problem $X$ is in co-NP if $\overline X$ is in NP. Here I have provided a yes-instance certificate for $\overline X$. Doesn't that mean $X$ is in co-NP? – Roshan SA Dec 3 '16 at 16:18
• The set $X$ is the set of graphs which have independent sets of size $s$. The set $\overline{X}$ is the set of graphs without an independent set of size $s$. The certificate you provide is for $X$, because it shows the independent set, if one exists. What you have to do to show that $\overline{X}\in NP$ is to give a certificate which somehow shows that all independent sets are smaller than $s$. It is not obvious what such a certificate would look like, but it is conceivable that you could come up with something clever. – Lieuwe Vinkhuijzen Dec 3 '16 at 16:56

Moreover, the complement problem would sound like "all independent sets have size at most $s$".
• If $X$ is NP-complete and it is in coNP then NP=coNP which is considered to be highly unlikely nowadays. And vice versa, if a problem is in NP and coNP this is usually considered as an evidence that it is not NP-complete – Eugene Dec 2 '16 at 7:13