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?

  • $\begingroup$ Downvoter, please explain what i missed here, or at least give a hint! $\endgroup$ Commented Feb 21, 2020 at 9:27
  • $\begingroup$ Apparently, I am a newbie in inapproximation $\endgroup$ Commented Feb 22, 2020 at 9:44
  • $\begingroup$ I did not downvote your question. I guess they think that your question is not a research-level since your are asking about the functions of gap-preserving reduction. $\endgroup$ Commented Feb 23, 2020 at 15:27
  • $\begingroup$ @MohammadAl-Turkistany Thank you. But, this seems to be the only way of justifying the proof given in the paper. If something else (such as an expander graph or an amplification) is involved, then the proof given has large holes. $\endgroup$ Commented Feb 24, 2020 at 4:02
  • 3
    $\begingroup$ You do not have to overcomplicate things here. It's just that since there is a correspondence between solution sizes, if you had an $f(n)$ approximation for the acyclic coloring problem, you could use it to get an $f(n)$ approximation for the coloring problem. So that means that acyclic coloring is at least as hard to approximate as coloring. $\endgroup$ Commented Feb 24, 2020 at 23:53

1 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.)

  • $\begingroup$ Also, by the way, the reduction they gave can be expressed as an L-reduction. But, approximation factor preserving reduction is simpler. $\endgroup$ Commented Feb 25, 2020 at 10:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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