Theoretical Computer Science
cc.complexity-theory circuit-complexity lower-bounds graph-colouring
Updated Wed, 01 Jun 2022 15:43:15 GMT

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

Comments (4)

  • +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  
  • +0 – @Jeigh: Yes, exactly as you said. (B.t.w. I wrongly duplicated the answer as a comment. I would like to remove one of them. Do somebody knows how to delete things?) — May 18, 2012 at 10:36  
  • +0 – Junkna, Thank you for your response. It seems that approximation methods can NOT capture the differences between k-clique problems and k-coloring problem in a parameterized complexity theoretic view which is stated in this question. Do you have any opinion or opposition about this my rough intuition? — May 18, 2012 at 11:35  
  • +0 – @Jeigh: No, we only know that lower bounds for k-Clique hold also for k-Coloring. But it may well be that the latter problem has another, more subtle positive and negative test inputs that are harder to separate (than those for Clique). Hence, it can well be that already 3-Coloring requires more than n^3 gates. — May 18, 2012 at 13:46  

References