Hardness of approximating acyclic chromatic number

Question

I have some doubts on the inapproximability result for acyclic coloring presented in the paper New acyclic and star coloring algorithms with application to computing Hessians. They claim that there exist an $\epsilon>0$ such that acyclic coloring cannot be approximated within $O(n^\epsilon)$ unless $\textsf{P=NP}$. It is proved by means of a reduction from Coloring.

Given an instance $G$ of Coloring, an graph $H$ is constructed by replacing each edge $e=uv$ of $G$ by $\Delta=\Delta(G)$ parallel edges and subdividing them exactly once. The construction has the following properties. They prove that for all $p$ in $3\leq p\leq \Delta$, $\chi(G)\leq p \iff \chi_s(H)\leq p$. From this, and the result Chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$, they conclude that Acyclic chromatic number is NP-hard to approximate within $O(n^\epsilon)$ for some $\epsilon>0$.

(In the above paragraph, $\Delta(G)$ denotes the maximum degree of $G$ ).

What type of reduction is this? I am assuming it is the basic type gap-preserving reduction presented in Vazirani's book (see quote below).

The details of the gap-preserving reduction are not clear to me. I think it is proved using a gap-preserving reduction.(Disclaimer: I don't know whether they are using some specific type of approximation preserving reduction such as L-reduction).
This is my best guess on the reduction. Clearly,
$\chi(G)\leq 3 \implies \chi_s(H)\leq 3$,
$\chi(G)>\Delta \implies \chi_s(H)>\Delta$

Let me recall definition for gap-preserving reduction from Vazirani's book here (slightly modified to fit this context).

A gap-preserving reduction from minimization problem A to minimization problem B with parameters $f,\alpha,g,\beta$ maps an instance $x$ of A to an instance $y$ of B such that
$\bullet\ $ the mapping is poly. time computable,
$\bullet\ $ $OPT\leq f(x) \implies OPT\leq g(y)$, and
$\bullet\ $ $OPT>\alpha(|x|)\ f(x) \implies OPT>\beta(|y|)\ g(y)$.

(Also for all $x$ and $y$, $\alpha(|x|)>1$ and $\beta(|y|)>1$. OPT refers to optimal value for problem A when used on left side, and problem B when used on right side.)

Here, it seems $f_A=f_B=3$ and $\alpha(|x|)=\beta(|y|)=\Delta/3$. But, here $|x|=n+m$ and $|y|=(n+\Delta m)+2\Delta m$ (where $n=$ #vertices in $G$, and $m=$ #edges in $G$). But then, functions $\alpha$ and $\beta$ cannot be defined like this!

What are the correct functions $f,g,\alpha,\beta$ implicit in the inpproximability proof of the paper?

Answer 1

It is not a gap-preserving reduction, but an approximation factor preserving reduction. The comment by Manuel Lafond is very close to an answer (but I cannot concur with the opinion that having same optimal values suffices; that is why I am writing this as an answer)

Quoting from Vazirani (the notation $s_1,s_2$ is mine):

Let $\Pi_1$ and $\Pi_2$ be two minimization problems. An approximation factor preserving reduction from $\Pi_1$ to $\Pi_2$ consists of two polynomial time algorithms, $f$ and $g$, such that

• for any instance $I_1$ of $\Pi_1$, $I_2 = f(I_1)$ is an instance of $\Pi_2$ such that
  OPT$_{\Pi_2}(I_2) \leq$ OPT$_{\Pi_1}(I_1)$, and
• for any solution $s_2$ of $I_2$, $s_1= g(I_1 ,s_2)$ is a solution of $I_1$ such that
  obj$_{\Pi_1}(I_1,s_1) \leq$ obj$_{\Pi_2}(I_2,s_2)$.

Note: obj$_{\Pi_1}(I_1,s_1)$ simply means the value of the objective function for instance $I_1$ for solution $s_1$. Here, for example it is the number of colours used by a colouring($s_1$) of a graph($I_1$).

The whole point of this reduction is that $\chi(G)=\chi_a(H)$. For $3\leq p\leq \Delta$, it is proved that $\chi(G)\leq p\iff \chi_a(H)\leq p$. Also, $\chi(G)\leq \Delta+1$ and $\chi_a(H)\leq \Delta+1$ (I wonder why they didn't mention the latter non-trivial fact in the proof). The choice of exactly $\Delta$ multilpe edges in the construction of $H$ plays a big role here.

I am told in person by someone working in the area that OPT$_{\Pi_1}(I_1)=$ OPT$_{\Pi_2}(I_2)$ suffices. But, I think this is not the case. If this were true, the definition of approximation factor preserving reduction can be simplified to the simple condition OPT$_{\Pi_1}(I_1)=$ OPT$_{\Pi_2}(I_2)$. Note that the 2nd condition implies that OPT$_{\Pi_1}(I_1) \leq$ OPT$_{\Pi_2}(I_2)$. I guess there must be a reason why they used a stronger condition in the definition. (As an evidence, many other approximation related reductions also demand mapping between objective value of solutions.)