<p>It is not a gap-preserving reduction, but an <strong>approximation factor preserving reduction</strong>. 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)</p>

<p>Quoting from Vazirani (the notation <span class="math-container">$s_1,s_2$</span> is mine):</p>

<blockquote>
  <p>Let <span class="math-container">$\Pi_1$</span> and <span class="math-container">$\Pi_2$</span> be two minimization problems. An approximation factor preserving reduction from <span class="math-container">$\Pi_1$</span> to <span class="math-container">$\Pi_2$</span> consists of two polynomial time algorithms, <span class="math-container">$f$</span> and <span class="math-container">$g$</span>, such that</p>
  
  <ul>
  <li>for any instance <span class="math-container">$I_1$</span> of <span class="math-container">$\Pi_1$</span>, <span class="math-container">$I_2 = f(I_1)$</span> is an instance of <span class="math-container">$\Pi_2$</span> such that<br>
  OPT<span class="math-container">$_{\Pi_2}(I_2) \leq$</span> OPT<span class="math-container">$_{\Pi_1}(I_1)$</span>, and</li>
  <li>for any solution <span class="math-container">$s_2$</span> of <span class="math-container">$I_2$</span>, <span class="math-container">$s_1= g(I_1 ,s_2)$</span> is a solution of <span class="math-container">$I_1$</span> such that<br>
  obj<span class="math-container">$_{\Pi_1}(I_1,s_1) \leq$</span> obj<span class="math-container">$_{\Pi_2}(I_2,s_2)$</span>.</li>
  </ul>
</blockquote>

<p>Note: obj<span class="math-container">$_{\Pi_1}(I_1,s_1)$</span> simply means the value of the objective function for instance <span class="math-container">$I_1$</span> for solution <span class="math-container">$s_1$</span>. Here, for example it is the number of colours used by a colouring(<span class="math-container">$s_1$</span>) of a graph(<span class="math-container">$I_1$</span>).</p>

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

<p>I am told in person by someone working in the area that OPT<span class="math-container">$_{\Pi_1}(I_1)=$</span> OPT<span class="math-container">$_{\Pi_2}(I_2)$</span> 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<span class="math-container">$_{\Pi_1}(I_1)=$</span> OPT<span class="math-container">$_{\Pi_2}(I_2)$</span>. Note that the 2nd condition implies that OPT<span class="math-container">$_{\Pi_1}(I_1) \leq$</span> OPT<span class="math-container">$_{\Pi_2}(I_2)$</span>. 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.)</p>

CC BY-SA 4.0
2020-02-25T10:11:38.673Z
Also, by the way, the reduction they gave can be expressed as an L-reduction. But, approximation factor preserving reduction is simpler.
Cyriac Antony
CC BY-SA 4.0
2020-02-25T10:09:48.413Z
2020-02-25T10:18:16.473Z
2020-02-25T10:18:16.473Z
Cyriac Antony
<p>I have some doubts on the inapproximability result for acyclic coloring presented in the paper <a href="https://www.eecs.wsu.edu/~assefaw/publications/acyclic-SISC.pdf" rel="nofollow noreferrer"><em>New acyclic and star coloring algorithms with application to computing Hessians</em></a>. They claim that there exist an <span class="math-container">$\epsilon&gt;0$</span> such that acyclic coloring cannot be approximated within <span class="math-container">$O(n^\epsilon)$</span> unless <span class="math-container">$\textsf{P=NP}$</span>. It is proved by means of a reduction from Coloring.</p>

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

<p>(In the above paragraph, <span class="math-container">$\Delta(G)$</span> denotes the maximum degree of <span class="math-container">$G$</span> ).</p>

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

<p>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).<br>
This is my best guess on the reduction. Clearly,<br>
<span class="math-container">$\chi(G)\leq 3 \implies \chi_s(H)\leq 3$</span>,<br>
<span class="math-container">$\chi(G)&gt;\Delta \implies \chi_s(H)&gt;\Delta$</span>  </p>

<p>Let me recall definition for gap-preserving reduction from <a href="https://www.springer.com/gp/book/9783540653677" rel="nofollow noreferrer">Vazirani's book</a> here (slightly modified to fit this context).  </p>

<blockquote>
  <p>A gap-preserving reduction from minimization problem A to minimization problem B with parameters <span class="math-container">$f,\alpha,g,\beta$</span> maps an instance <span class="math-container">$x$</span> of A to an instance <span class="math-container">$y$</span> of B such that<br>
  <span class="math-container">$\bullet\ $</span> the mapping is poly. time computable,<br>
  <span class="math-container">$\bullet\ $</span> <span class="math-container">$OPT\leq f(x) \implies OPT\leq g(y)$</span>, and<br>
  <span class="math-container">$\bullet\ $</span> <span class="math-container">$OPT&gt;\alpha(|x|)\  f(x) \implies OPT&gt;\beta(|y|)\ g(y)$</span>.</p>
</blockquote>

<p>(Also for all <span class="math-container">$x$</span> and <span class="math-container">$y$</span>, <span class="math-container">$\alpha(|x|)&gt;1$</span> and <span class="math-container">$\beta(|y|)&gt;1$</span>. OPT refers to optimal value for problem A when used on left side, and problem B when used on right side.)</p>

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

<p><strong>What are the correct functions <span class="math-container">$f,g,\alpha,\beta$</span> implicit in the inpproximability proof of the paper?</strong></p>

CC BY-SA 4.0
2020-02-21T09:27:44.490Z
Downvoter, please explain what i missed here, or at least give a hint!
Cyriac Antony
CC BY-SA 4.0
2020-02-22T09:44:27.457Z
Apparently, I am a newbie in inapproximation
Cyriac Antony
CC BY-SA 4.0
2020-02-23T15:27:41.667Z
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.
Mohammad Al-Turkistany
CC BY-SA 4.0
2020-02-24T04:02:34.433Z
@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.
Cyriac Antony
CC BY-SA 4.0
2020-02-24T23:53:30.650Z
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.
Manuel Lafond
<approximation-hardness>
Hardness of approximating acyclic chromatic number
Cyriac Antony
# Hardness of approximating acyclic chromatic number

(Asked by: username_0 on 2020-02-20)

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*](https://www.eecs.wsu.edu/~assefaw/publications/acyclic-SISC.pdf). 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](https://www.springer.com/gp/book/9783540653677) 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?**

**Tags:** approximation-hardness
> **Comments:**
> **username_0**: Downvoter, please explain what i missed here, or at least give a hint!  
> **username_0**: Apparently, I am a newbie in inapproximation  
> **username_1**: 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.  
> **username_0**: @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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_0 on 2020-02-25. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: Also, by the way, the reduction they gave can be expressed as an L-reduction. But, approximation factor preserving reduction is simpler.  

---

