Is it apx-hard to approximate fractional chromatic number on bounded degree graphs?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What is fractional chromatic number? $\endgroup$– Mohammad Al-TurkistanyCommented Nov 2, 2011 at 10:07
-
5$\begingroup$ @MohammadAl-Turkistany: LP relexation of chromatic number, see, e.g., en.wikipedia.org/wiki/Fractional_coloring $\endgroup$– Jukka SuomelaCommented Nov 2, 2011 at 11:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Yes.
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:
- There is a $k$-colouring.
- 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:
- The fractional chromatic number is at most $k$.
- 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.
answered Nov 2, 2011 at 10:36
-
$\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$ Commented Nov 2, 2011 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$ Commented Nov 2, 2011 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$ Commented Nov 2, 2011 at 19:37
-
$\begingroup$ @AndrewD.King: Yes, I'll edit the answer; it'll hopefully make more sense that way. :) $\endgroup$ Commented Nov 2, 2011 at 19:56