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.


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

  • $\begingroup$ I accepted the answer based on the first part. But note that the link you provide is about maximum independent set, whereas my problem fixes the size of the set and tries to find the set with minimum "dependence", that is, such that the number of induced edges is minimized. $\endgroup$ Jun 8, 2021 at 13:09
  • 1
    $\begingroup$ Sorry, as well as that link being to the wrong problem, including it in the first place was born of the mistaken idea that (1) actually holding was necessary for the proof to work. Fixed now. $\endgroup$ Jun 8, 2021 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.