Return to Question

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?

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

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?

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?