0
$\begingroup$

I am new to the complexity theory and I am trying to understand what would be the complexity of the following problem: "Is a graph AT LEAST $k$-colorable?"

Whether a graph is $k$-colorable is clearly a NPC problem and is explained by reduction to 3-SAT.

However, I am not sure to which complexity class belongs the modified problem I have stated. Does it belong to NP as well? My guess is that we would be able to check it with a polynomial certificate (any $\geq k$ coloring of the graph).

And then the problem "Is a graph AT MOST $k$-colorable?" would be its complement in co-NP unless NP=co-NP?

$\endgroup$
2
  • $\begingroup$ Could you give an example of a graph that is not "at least 3-colorable"? $\endgroup$ – Tom van der Zanden Sep 7 '20 at 21:23
  • $\begingroup$ Tom: probably any graph with 0, 1, or 2 nodes. $\endgroup$ – gnasher729 Sep 8 '20 at 21:29
0
$\begingroup$

Well, all graphs are colorable with $\geq k$ colors: Assign each vertex a different color (and leave the other color classes empty if $k$ is larger than the number of vertices of the given graph).

As for the complement of this problem, note that you did not correctly invert the definition of the problem: A problem $L$ is, after all, merely a set of strings over some finite alphabet $\Sigma$ representing some objects with some property. Its complement is then the set $\Sigma^\ast \setminus L$ or the set of all strings not representing an object with the property. If we recall the argument above, we find that the complement of your problem is hence the set of all strings not representing graphs (under that fixed encoding scheme) rather than the one you claimed. This problem (as the first one), is in $\mathsf P$.

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