1
$\begingroup$

Let's denote $IS(G)$ to be the size of the maximal independent set in $G$. Consider the following language: $$A = \left \{ G\ |\ IS(G)\ge \frac{1}{5}n \right \}$$

I know that $gap-IS [1/8 + \varepsilon , 1/4-\varepsilon]$ is $NP$-hard.

How can I infer that $A$ is $NP$-hard by utilizing the gap problem?

$\endgroup$
1
$\begingroup$

You reduce $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ (for any $\epsilon < 1/20$) to $A$. The reduction is the identity function. Let's see why it works:

  • If a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has an independent set of size at least $(1/4-\epsilon)n \geq n/5$.
  • If a graph $G$ is a NO instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ then it has no independent set of size $(1/8+\epsilon)n < n/5$.

Hence a graph $G$ is a YES instance of $\text{gap-IS}[1/8+\epsilon,1/4-\epsilon]$ if and only if it is a YES instance of $A$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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