<p>Suppose you have a reduction $f$ from problem $A$ to problem $B$. So if $f(x) \in B$ then $x \in A$ and if $f(x) \notin B$ then $x \notin A$ (here $x \in A$ means $x$ is a YES instance of $A$).</p>

<p>Now suppose that $A$ and $B$ are in fact optimization problems, say both are maximization problems. Now $f$ maps an instance $(x,a)$ of $A$ to an instance $(y,b)$ of $B$ such that $B(y) \geq b$ implies $A(x) \geq a$ and $B(y) &lt; b$ implies $A(x) &lt; a$ (here $A(x)$ is the optimal value of $x$ for problem $A$).</p>

<p>Suppose you had an approximation algorithm $O$ for $B$, say with approximation ratio $\rho &lt; 1$. Then $O(y) \geq \rho B(y)$. How would you convert this to an approximation algorithm for $A$? There are two problems:</p>

<ol>
<li>$O$ only gives a solution for $B$ problems. You will need another procedure $P$ that converts a solution for $y$ to a solution for $x$.</li>
<li>You need a promise that if the solution produced by $O$ is good as a solution for $y$, then the solution produced by applying $P$ is good for $x$.</li>
</ol>

<p>When these two conditions are satisfied, the reduction preserves approximability, and then the implication is correct. But they need not hold in general.</p>

<p>Here is a concrete example. A set of vertices in a graph is a <em>vertex cover</em> iff its complement is an <em>independent set</em>. While vertex cover has a $2$-approximation algorithm, independent set is (probably) not approximable. Here the reductions $f$ and $P$ are trivial - given a graph $G$ with $n$ vertices and a threshold $a$ for independent set, $f$ outputs the same graph $G$ and the threshold $b=n-a$ for vertex cover. The conversion procedure $P$ simply complements the solution.</p>

<p>Consider the $2$-approximation algorithm for vertex cover (which is a minimization problem). Thus, if the graph $G$ has a vertex cover of size $T$, then it returns a vertex cover of size $2T$. In terms of the optimal independent set, we go from $n-T$ to $n-2T$. This could be a big difference for some values of $T$: for example, if $T = n/2$, then there is an independent set containing half the vertices, but this reduction only gives us an independent set of size $0$!</p>

<p>Finally, there are logspace reductions among most well-known NP-complete problems, including probably independent set and MAX-CUT. Since logspace reductions compose, all you need to do is follow the chain of reductions and verify that all of them are logspace.</p>

CC BY-SA 3.0
2013-09-11T19:12:59.397Z
So just an addendum: are there any conditions like conditions $1$ and $2$ for AP reduction (asking this since you have the implication for AP reductions)?
Turbo
CC BY-SA 3.0
2013-09-12T03:53:03.993Z
Yes, these are indeed called approximation-preserving reductions or APX reductions, and they are just a formal version of conditions 1 and 2. You need the procedure $P$, and then a promise that if the original solution was $1+\epsilon$-optimal then after applying $P$ the new solution is $1+O(\epsilon)$-optimal. You can think of other notions of reductions, depending on what notion of approximability you're interested int. (For example, instead of $1+\epsilon \to 1+O(\epsilon)$ we could have $\alpha \to O(\alpha)$.)
Yuval Filmus
CC BY-SA 3.0
2013-09-10T14:25:25.870Z
2013-09-10T14:25:25.870Z
Yuval Filmus
<p>Given optimization problems $P1$ and $P2$. The slides below say that, $P1 \leq_L P2$ does not imply $P2 ∈ APX$, then $P1 ∈ APX$. Why is this so?
<a href="http://www.di.univr.it/documenti/AttDidAva/allegato/allegato581250.pdf" rel="nofollow">http://www.di.univr.it/documenti/AttDidAva/allegato/allegato581250.pdf</a></p>

<p>$MAX INDEP SET$ is not in APX while $MAX CUT$ is.</p>

<p>Is an L reduction, $MAX INDEP SET$ $\leq_L$ $MAX CUT$ possible? The above implication does not say this is impossible.</p>

<p>Is there an inspiration to understand this from why $MAX INDEP SET$ is not in APX while $MAX CUT$ is?</p>

CC BY-SA 3.0
2013-09-10T14:25:49.150Z
More appropriate for cs.stackexchange.
Yuval Filmus
CC BY-SA 3.0
2013-09-10T22:24:17.003Z
you have to be in pretty exclusive company to think that L-reductions (and approximations in general) should be cs.SE.
Suresh Venkat
<cc.complexity-theory><apx>
On APX problems
Turbo
# On APX problems

(Asked by: username_0 on 2013-09-10)

Given optimization problems $P1$ and $P2$. The slides below say that, $P1 \leq\_L P2$ does not imply $P2 ∈ APX$, then $P1 ∈ APX$. Why is this so?
<http://www.di.univr.it/documenti/AttDidAva/allegato/allegato581250.pdf>

$MAX INDEP SET$ is not in APX while $MAX CUT$ is.

Is an L reduction, $MAX INDEP SET$ $\leq\_L$ $MAX CUT$ possible? The above implication does not say this is impossible.

Is there an inspiration to understand this from why $MAX INDEP SET$ is not in APX while $MAX CUT$ is?

**Tags:** cc.complexity-theory, apx

> **Comments:**
> **username_1**: More appropriate for cs.stackexchange.  
> **username_2**: you have to be in pretty exclusive company to think that L-reductions (and approximations in general) should be cs.SE.  

---

## 1 answers

### Answer by username_1 on 2013-09-10. Score: 7 | Accepted answer

Suppose you have a reduction $f$ from problem $A$ to problem $B$. So if $f(x) \in B$ then $x \in A$ and if $f(x) \notin B$ then $x \notin A$ (here $x \in A$ means $x$ is a YES instance of $A$).

Now suppose that $A$ and $B$ are in fact optimization problems, say both are maximization problems. Now $f$ maps an instance $(x,a)$ of $A$ to an instance $(y,b)$ of $B$ such that $B(y) \geq b$ implies $A(x) \geq a$ and $B(y) < b$ implies $A(x) < a$ (here $A(x)$ is the optimal value of $x$ for problem $A$).

Suppose you had an approximation algorithm $O$ for $B$, say with approximation ratio $\rho < 1$. Then $O(y) \geq \rho B(y)$. How would you convert this to an approximation algorithm for $A$? There are two problems:

1. $O$ only gives a solution for $B$ problems. You will need another procedure $P$ that converts a solution for $y$ to a solution for $x$.
2. You need a promise that if the solution produced by $O$ is good as a solution for $y$, then the solution produced by applying $P$ is good for $x$.

When these two conditions are satisfied, the reduction preserves approximability, and then the implication is correct. But they need not hold in general.

Here is a concrete example. A set of vertices in a graph is a *vertex cover* iff its complement is an *independent set*. While vertex cover has a $2$-approximation algorithm, independent set is (probably) not approximable. Here the reductions $f$ and $P$ are trivial - given a graph $G$ with $n$ vertices and a threshold $a$ for independent set, $f$ outputs the same graph $G$ and the threshold $b=n-a$ for vertex cover. The conversion procedure $P$ simply complements the solution.

Consider the $2$-approximation algorithm for vertex cover (which is a minimization problem). Thus, if the graph $G$ has a vertex cover of size $T$, then it returns a vertex cover of size $2T$. In terms of the optimal independent set, we go from $n-T$ to $n-2T$. This could be a big difference for some values of $T$: for example, if $T = n/2$, then there is an independent set containing half the vertices, but this reduction only gives us an independent set of size $0$!

Finally, there are logspace reductions among most well-known NP-complete problems, including probably independent set and MAX-CUT. Since logspace reductions compose, all you need to do is follow the chain of reductions and verify that all of them are logspace.

> **Comments:**
> **username_0**: So just an addendum: are there any conditions like conditions $1$ and $2$ for AP reduction (asking this since you have the implication for AP reductions)?  
> **username_1**: Yes, these are indeed called approximation-preserving reductions or APX reductions, and they are just a formal version of conditions 1 and 2. You need the procedure $P$, and then a promise that if the original solution was $1+\epsilon$-optimal then after applying $P$ the new solution is $1+O(\epsilon)$-optimal. You can think of other notions of reductions, depending on what notion of approximability you're interested int. (For example, instead of $1+\epsilon \to 1+O(\epsilon)$ we could have $\alpha \to O(\alpha)$.)  

---

