Recall the notion of NPO problem. An NPO problem is simple if the following is true:

$\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$

In words, given any positive integer $k$, the problem of deciding if for instance $x$ its optimal is less or equal than k is in $P$.

I'm asked to show the MAXIMUM CLIQUE problem is simple and that assuming $P \neq NP$ MINIMUM GRAPH COLORING is not simple.


This is problem 3.13 of "Complexity and Approximation" of Ausiello et alii.

  • 1
    $\begingroup$ Brute forcing k-clique already is in P. But 3-coloring is not: it is the same as 3SAT. $\endgroup$
    – rus9384
    Sep 1, 2017 at 20:24

1 Answer 1


$k-Clique$ is in $\mathsf P$. More precisely, this can be done in $O(|V|^k)$ time. How? If you have a set of power $|V|$, then, how many subsets of power $k$ does it contain? Answer is $C^k_{|V|}\in O(|V|^k)$.

$3-Coloring$ is $\mathsf{NP}$-complete and reduction is well described in this paper. Since SAT can be reduced to 3SAT, any Coloring also can be reduced to 3-Coloring.


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.