3
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ 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)? $\endgroup$ – T.... Sep 11 '13 at 19:12
  • 2
    $\begingroup$ 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)$.) $\endgroup$ – Yuval Filmus Sep 12 '13 at 3:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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