7
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ k-coloring is not a monotone function, it cannot be computed by a monotone circuit. $\endgroup$ – Kaveh May 17 '12 at 20:17
  • 3
    $\begingroup$ @Kaveh: k-coloring is monotone downward - if a graph has a k-coloring, then so does any subgraph. So non-k-colorability could be computed by a monotone circuit. $\endgroup$ – Joshua Grochow May 17 '12 at 20:19
  • $\begingroup$ @Joshua, good point, we can also change the representation of the input, representing existence of edges by 0, I guess that would be an easier way to deal with the monotonicity issue. $\endgroup$ – Kaveh May 17 '12 at 20:25
  • $\begingroup$ Hi, Kaveh and Grochow $\endgroup$ – Jeigh May 18 '12 at 1:18
  • 4
    $\begingroup$ @Jeigh please take the time to proofread your posts and fix obvious spelling errors. (if you're using a browser like firefox, it will even indicate where the errors are). $\endgroup$ – Suresh Venkat May 18 '12 at 2:49
8
$\begingroup$

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

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – Jeigh May 18 '12 at 10:18
  • $\begingroup$ @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?) $\endgroup$ – Stasys May 18 '12 at 10:36
  • $\begingroup$ 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? $\endgroup$ – Jeigh May 18 '12 at 11:35
  • $\begingroup$ @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. $\endgroup$ – Stasys May 18 '12 at 13:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.