Inapproximability of graph problems on a restricted setting

Question

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

1. There is a constant $\rho > 1$ such that $\mathcal{P}$ cannot be approximated by a factor better than $\rho$.
2. 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.

Answer 1

Yes, $(1) \implies (2)$. Suppose towards contradiction that $(1)$ is true but $(2)$ is false. Negating $(2)$ gives

$\forall \rho' > 1 \exists c > 0$ such that the problem $cP$ can be approximated by a factor better than $\rho'$ in time polynomial in the vertex count.

(I added "in time polynomial in the vertex count", since without a restriction like this you could of course solve the problem exactly in exponential time.)

Let $c_{\rho'}$ be a value of $c$ that works for $\rho'$ (the negation of $(2)$ makes this well-defined for each $\rho'$). Now arbitrarily good $\rho'$-approximations can be made to the original problem in time polynomial in the number of vertices: Just keep adding vertices that are adjacent to every other vertex until $|V(G)| \ge c_{\rho'}k$ and then solve using the approximation algorithm for the restricted problem. If the solution contains any of the added vertices, swap each one with any original vertex -- this cannot make the solution worse.

Note that the above approximation algorithm is polynomial in the original number $n$ of vertices even if $c_{\rho'}$ is very large, e.g., superexponential in $\rho'$, because for $k, \rho'$ fixed and $n$ large enough, $n \ge c_{\rho'}k$ so no vertices need to be added.

The existence of a poly-time $\rho'$-approximation for the original unrestricted problem and for arbitrary $\rho'$ contradicts $(1)$ (specifically, you could choose, e.g., $\rho' = (1+\rho)/2$), so it must be that $(1) \implies (2)$.

(Aside: It's not necessary for $(1)$ to hold for the above proof to go through, but if $\textrm P \ne \textrm{NP}$, it does anyway, since if a poly-time $\rho$-approximate algorithm for your problem for arbitrary $\rho > 1$ existed, you could use it to solve Maximum Independent Set exactly in poly-time: Choose any $\rho > 1$ and run the $\rho$-approximate algorithm for your problem inside a binary search on $k$ until we find the largest $k$ for which it reports an answer of 0. Since the approximation ratio is defined multiplicatively, the true answer for this $k$ must also be 0, and since $A(G, k) \ge OPT(G, k)$, the true answer for $k+1$ is $> 0$, so $k$ is the size of a largest IS.)