I am considering the following problem $\mathcal{P}$.
$\mathcal{P}$: Given an undirected graph $G$, and an integer $k$, find a set of vertices $S \subseteq V(G)$, with $|S| = k$, such that the number of edges in the subgraph induced by $S$ is minimized.
which is clearly NP-hard, as the answer is 0 iff there is an independent set of size $k$ in $G$. So I am interested in studying whether the problem can be approximated assuming $\mathrm{P} \neq \mathrm{NP}$ (assumption implicit from now on). More precisely, saying that $\mathcal{P}$ cannot be approximated by a factor better than $\rho$ means that there is no constant $\alpha < \rho$ for which a polytime algorithm $A$ can guarantee that $A(G, k) \leq \alpha \mathrm{OPT}(G,k)$ for every input $G, k$.
Now, for the restricted setting, imagine $c > 0$ is an arbitrary constant, and then define $c\mathcal{P}$ as the same problem but with the restriction that $|V(G)| \geq c \cdot k$. The question I am wondering is whether, given the following claims 1) and 2), it is true that 1) implies 2).
- There is a constant $\rho > 1$ such that $\mathcal{P}$ cannot be approximated by a factor better than $\rho$.
- There is a constant $\rho' > 1$ such that for any constant $c > 0$ the problem $c\mathcal{P}$ cannot be approximated by a factor better than $\rho'$.
I would appreciate any help, or pointers to problems when something like that is proven.