Approximation Algorithm between two NP compete problems

Question

Suppose that a O(n²)-time alpha-approximate algorithm exists for one of the two problems in each of the following pairs:

• Vertex Cover and Independent Set
• Independent Set and Clique
• Max-Flow and Min-Cut

Does this guarantee that a O(n²)-time alpha-approximate algorithm exists for the other problem in the pair? I know that Clique reduces to Independent Set which in turn reduces to Vertex Cover.

Answer 1

Not necessarily, for two reasons.

First of all, NP reductions are generally not linear in complexity. Some of them are, but usually a problem of complexity n will reduce to some other NP problem of size n^3 or something. Even if we found a linear-time 3SAT algorithm, we wouldn't have found linear-time algorithms for all NP-hard problems -- just polynomial algorithms. So if by "similar" you mean "also n^2", not in general.

Secondly, approximations don't generally transfer. Because of the non-linear growth in complexity (that's a simplification of why, but it'll do), approximation guarantees generally don't survive the reduction process. As a result, while all NP-complete problems are in a sense comrades in exact solution hardness, they are far from it in approximation hardness.

In certain specific cases, approximations do transfer (and one of your examples -- left as an exercise for the reader -- most definitely transfers). But it's in no way guaranteed.