Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?



If I understood correctly, the proof of Theorem 1.6 in Khot (2001) establishes that it is NP-hard to distinguish between the following two cases, even if we focus on bounded-degree graphs of sufficiently high degree:

  1. There is a $k$-colouring.
  2. The ratio of the number of vertices to the maximum size of an independent set is at least $k^{\log(k)/25}$.

From the perspective of fractional chromatic number these two cases are:

  1. The fractional chromatic number is at most $k$.
  2. The fractional chromatic number is at least $k^{\log(k)/25}$.

Now we must remember that we need sufficiently high degrees (as a function of $k$). But as far as I can see, the proof has, e.g., the following convenient corollary that might already be sufficient for your purposes:

  • Given any constant $\alpha$, there are constants $\Delta$ and $c$ such that the following problem in NP-hard: given a graph $G$ of maximum degree $\Delta$, decide whether the fractional chromatic number of $G$ is at most $c$ or at least $\alpha c$.

An of course this already implies that there is no PTAS, unless P = NP.

  • $\begingroup$ Surely the last corollary has some other modifiers on the constants, otherwise this is very well known for small values of $\Delta$, $c_1$, and $c_2$... $\endgroup$ – Andrew D. King Nov 2 '11 at 15:03
  • $\begingroup$ @AndrewD.King: Right, you can make any of them arbitrarily large, etc. But perhaps you could post an answer that shows that the simple version of the corollary can be derived by using older and easier techniques – I think it would already be sufficient to answer OP's question? $\endgroup$ – Jukka Suomela Nov 2 '11 at 15:10
  • $\begingroup$ @JukkaSuomela I mean that as stated, this does not prove APX-hardness. E.g. it is well-known (Holyer, SICOMP, 1980) that determining the chromatic index of a cubic graph is NP-hard, meaning that it is NP-hard to determine whether or not the chromatic number of a line graph with maximum degree 4 is 4. What I think you mean is: Given any constant $k$, there exist constants $\Delta$, $c_1$, and $c_2$ such that $kc_1<c_2$,... Is that right? $\endgroup$ – Andrew D. King Nov 2 '11 at 19:37
  • $\begingroup$ @AndrewD.King: Yes, I'll edit the answer; it'll hopefully make more sense that way. :) $\endgroup$ – Jukka Suomela Nov 2 '11 at 19:56

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.