# Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

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.

References

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

• Brute forcing k-clique already is in P. But 3-coloring is not: it is the same as 3SAT. – rus9384 Sep 1 '17 at 20:24

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