Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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$.
share|improve this answer
    
Thanks for your answering. If I understand it right, what you said is that NTM can construct and check a coloring in polynomial time, so that this must be a NP problem, right? FYI: What I want to ask is just whether this is a NP problem or not. –  babysnow Dec 17 '12 at 3:31
    
Yes, that is what I said. –  MJD Dec 17 '12 at 3:39

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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