show that careful 5COLOR is in NP

Question

We know that 5COLOR problem is NP-complete. careful 5COLOR problem is that: Given a graph G, can we color each vertex with an integer from the set {0,1,2,3,4}, so that for each edge, the colors of the two endpoints differ by exactly 1 modulo 5.

Can we show that careful 5COLOR is in NP?

Answer 1

The way you show that anything is in NP is pretty much the same. It always has the form "The nondeterministic Turing machine should guess a solution, and then it can check (in polynomial time) that the solution is correct."

In this case it looks like this: "The nondeterministic Turing machine should guess a coloring of the vertices of $G$, and then check in polynomial time that for each edge of $G$, its two endpoints have colors that satisfy the given condition."

The important details that you must establish are:

1. Can the NTM really construct the coloring in polynomial time? In this case yes, since the coloring is just an assignment of integers to the vertices, and the number of vertices is bounded by a polynomial in the size of $G$.
2. Can the NTM really check in polynomial time whether the condition is satisfied for every pair of vertices that are connected by an edge? Yes, because each check takes constant time, and the number of checks is equal to the number of edges in $G$, which is bounded by a polynomial in the size of $G$.

Answer 2

Alternatively, if we take the definition of NP as the class of problems that can be verified in polynomial time, we can see that Careful 5-COL is in NP because there is a deterministic Turing machine that can check an answer in polynomial time.

In particular, given an instance $G$, we can take a certificate that $G$ is carefully 5-colorable as a function $f:V(G)\rightarrow \{0,\ldots,4\}$. Given this function, we can take each edge $uv$, and check that $f(v)-f(u) \equiv 1 (5)$. We only have to look at each edge once, so the algorithm to check is $O(|E|)$ (even if we're nasty about how $f$ is encoded, it's still something like $O(|E|\times|V|)$).