# On APX problems

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?

• More appropriate for cs.stackexchange. – Yuval Filmus Sep 10 '13 at 14:25
• you have to be in pretty exclusive company to think that L-reductions (and approximations in general) should be cs.SE. – Suresh Venkat Sep 10 '13 at 22:24

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.

• 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)? – T.... Sep 11 '13 at 19:12
• 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 Sep 12 '13 at 3:53