2
$\begingroup$

As far as I know, the K coloring problem is NP-complete. However, I'm a bit confused about how to determine whether a problem is weakly or strongly NP-complete.

  • If an NP-complete problem is decidable by a pseudo-polynomial time algorithm, it is called weakly NP-complete.
  • If an NP-complete problem's unary version is NP-complete, then it is called strongly NP-complete.

Is there a straightforward proof that the K coloring problem is weakly or strong NP-complete?

$\endgroup$

1 Answer 1

1
$\begingroup$

There are no obvious integers involved in an instance of the $K$-coloring problem (where $K$ is part of the problem and not of the input).

The length of the encoding of an instance of $K$-coloring is the length of the encoding of the graph. The standard reduction from 3-SAT shows that the problem is (strongly) NP-complete.

Even if $K$ were part of the input, this would have no effect on the asymptotic size of the encoding of the input (since only $K \le n$ makes sense, where $n$ is the number of nodes of the graph).

$\endgroup$
13
  • $\begingroup$ I want to prove that the 4-Coloring Problem is strongly NP-complete. How can I create an unary version for the 4-Coloring Problem? $\endgroup$
    – wellknow
    Commented Jan 17 at 13:00
  • $\begingroup$ "Unary version: when numbers are represented in unary on the input, for example, 3 is represented as 111, 4 is represented as 1111, etc." $\endgroup$
    – wellknow
    Commented Jan 17 at 13:30
  • $\begingroup$ What numbers are you referring to? $\endgroup$
    – Steven
    Commented Jan 17 at 13:40
  • $\begingroup$ For example: Assign to each vertex a sequence of ones indicating the corresponding color.For example, if the first vertex is assigned the first color, let it be "1". If the second vertex is assigned the third color, let it be "111". Therefore, each vertex is represented by a sequence of ones, and this sequence is provided in unary encoding. For instance, if the coloring of vertices looks like this: red = 1, blue = 11, green = 111, yellow = 1111 . Then: Vertex 1: Blue -> 11, Vertex 2: Red -> 1, Vertex 3: Green -> 111, Vertex 4: Yellow -> 1111 $\endgroup$
    – wellknow
    Commented Jan 17 at 13:47
  • $\begingroup$ The color of the vertices is not part of the input though. $\endgroup$
    – Steven
    Commented Jan 17 at 14:11

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.