Approximation ratio when optimal solution is $0$

Question

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?

Answer 1

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

Answer 2

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