Theoretical Computer Science

# Razborov's Approximation methods

The approximation mothods is used for deriving lower bounds on the monotone circuit size of k-cliue and perfect matching problem.

People in parameterized complexity theory strongly believe that k-colooring is strictly harder than the k-clique problem, because k-clique problems can be solved by an exhaustive search of all ${n \choose k}$ potential cliques while k-coloring is NP-complete for a fixed k (k=3). k-coloring is also monotone function.

It seems to be natural that the approx method is appropriate for deriving lower bounds of the problem but I haven't seen a paper which justifies this intuition.

Is Razborov's method useful to derive the exponential monotone lower bound of k-coloring?

## Solution

Let $f(G)=1$ iff $G$ is not $(k-1)$-colorable. Then $f$ accepts all $k$-cliques, and rejects all complete $(k-1)$-partite graphs, just like the $k$-clique function does. So, the lower bounds for clique hold also for $f$.

• +0 – Hi Jukna, is your statement that we can take $k$-cliques as "positive test inputs" and $(k-1)$-partite graphs as "negative inputs" and lower bound is the same value $2^{\varepsilon \sqrt{k}}$ of $k-clique$ lower bound ? — May 18, 2012 at 10:18