6
$\begingroup$

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to enumerate the vertices of $G$ and delete any vertex that if your decision function tells you is not in the clique) But for 3-COLOR problem, I have no idea of how to link decision problem to search problem. Can anybody help me?

$\endgroup$
4
$\begingroup$

Let the vertices of the input graph $G$ be $\{v_1, \dots, v_n\}$. First, check if $G$ is 3-colourable: if not, output "No 3-colourings" and quit.

Otherwise, add new vertices called $r$, $g$ and $b$ to $G$ and add the edges $rb$, $bg$ and $br$. Call this graph $G_0$. Note that $G_0$ is 3-colourable and, in any 3-colouring of $G_0$, the three new vertices must receive different colours. Since the names of the colours are arbitrary, we will call the colour that $r$ gets, red; call $g$&'s colour, green; and call $b$'s colour blue.

We'll now create a sequence of graphs $G_1, \dots, G_n$, each of which will be 3-colourable, creating $G_i$ from $G_{i-1}$ as follows.

  • Set $G_i = G_{i-1} + \{rv_i, gv_i\}$ (i.e., the graph made by adding edges $rv_i$ and $gv_i$ to $G_{i-1}$) if this graph is is 3-colourable. Since $v_i$ is adjacent to both $r$, which is red, and $g$, which is green, $v_i$ must be blue.
  • Otherwise, set $G_i = G_{i-1} + \{gv_i, bv_i\}$, if this graph is 3-colourable. In this case, $v_i$ must be red.
  • Otherwise, set $G_i = G_{i-1} + \{bv_i, rv_i\}$. Since $G_{i-1}$ was 3-colourable (you can prove this by induction), and we couldn't find a colouring with $v_i$ blue or red, $v_i$ must be green.

The above procedure produces a 3-colouring of the $n$-vertex graph $G$ with $2n+1$ calls to the oracle (procedure) for checking 3-colourability.

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