The approximability behaviour of some combinatorial problems with respect to the approximability of a class of maximum independent set problems

We prove that the existence of a polynomial time ρ-approximation algorithm (where ρ < 1 is a fixed constant) for a class of independent set problems, leads to a polynomial time approximation algorithm with approximation ratio strictly smaller than 2 for vertex covering, while the non-existence of such an algorithm induces a lower bound on the ratio of every polynomial time approximation algorithm for vertex covering. We also prove a similar result for a (maximization) convex programming problem including quadratic programming as subproblem.