1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Dec 2, 2016 at 12:21
  • $\begingroup$ @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? $\endgroup$
    – Roshan SA
    Commented Dec 3, 2016 at 16:18
  • $\begingroup$ 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. $\endgroup$
    – Lieuwe Vinkhuijzen
    Commented Dec 3, 2016 at 16:56

1 Answer 1

Reset to default
2
$\begingroup$

Independent set is NP-complete, so it's unlikely to be in coNP.

Moreover, the complement problem would sound like "all independent sets have size at most $s$".

Improve this answer
$\endgroup$
3
  • $\begingroup$ Maybe this is not in Co-NP but does is it always mean If X is NP-complete then it is in coNP? $\endgroup$
    – Roshan SA
    Commented Dec 2, 2016 at 5:11
  • 2
    $\begingroup$ 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 $\endgroup$
    – Eugene
    Commented Dec 2, 2016 at 7:13
  • $\begingroup$ Isn't vertex cover the complement of indipendent set? $\endgroup$
    – exSnake
    Commented Jun 21, 2022 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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