This might be a basic technicality but I'd like to make sure how to handle it. The question is: how do we measure an algorithm's approximation (multiplicative) factor on instances with optimal value $0$.

Suppose I have a minimization problem $Pb$, and it is NP-Hard to decide if a given instance $I$ has optimal value $OPT(I) = 0$.

As a concrete example, say that $Pb$ is the problem of removing a minimum number of edges from a graph so that it is $3$-colorable. Deciding if $0$ edges suffice is NP-hard.

Suppose now that I have an approximation algorithm $A$ for $Pb$ that runs in polynomial time. How could $A$ achieve any kind of approximation factor?
Suppose $A$ always finds a solution of value $APP(I)$ within factor $\alpha$. Then on instances of value $0$ it must return a value $APP(I) \leq \alpha \cdot OPT(I) = 0$. Thus $APP(I)$ decides whether $OPT(I) = 0$. Unless $P = NP$, this is impossible and so $A$ cannot approximate $Pb$ within any factor in polynomial time, let it be constant, $poly(n)$, superexponential in $n$, whatever...

Is that it? Or is there some way around this technicality?


That's right. Such a problem is not approximable to within any constant factor large than 1 (unless P=NP).

Is there a way around this? Yes, there are several possibilities:

  1. Use a different measure of approximation, rather than multiplicative factor. For instance, you could consider its additive approximability.

  2. Re-define the problem so it cannot have output of 0. For instance, let $Pc(G)=Pb(G)+1$, i.e., $Pc$ is the problem of computing the minimum number of edges to remove from a graph so it becomes 3-colorable, plus one. Then there is no such barrier to achieving some constant approximation factor. (There might still be other barriers, of course.) Suppose you found that $Pc$ has a 2-approximation. Then you could unfold what that implies for $Pb$.

  • $\begingroup$ Good, that makes sense. Thank you for the clear answer. $\endgroup$ – Manuel Lafond Aug 14 '16 at 19:30

This is correct. $P$ (that is quite an unfortunate name for a problem if you also want to talk about $P$ as a class of problems) can not be approximated within any constant factor unless $P=NP$.

  • $\begingroup$ True about the notation, I call it $Pb$ now. So, I guess we can extend the reasoning to say that $Pb$, with instance size $n$, cannot be approximated within factor $poly(n)$, $2^n$, $2^{n^{n^n}}$? That is, no approximation can even exist then? This feels weird, since in the example problem the maximum number of edges to delete is bounded... $\endgroup$ – Manuel Lafond Aug 6 '16 at 23:10
  • $\begingroup$ It can be approximated within factor $1$, just not in polynomial time. $\endgroup$ – Tom van der Zanden Aug 8 '16 at 16:03

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.