2
$\begingroup$

I want to prove that the NP-hardness of Maximum Independent Set implies that there is no FPTAS for the Maximum Independent Set problem unless $P=NP$.

I found the following approach after some research online:

Assuming that such an FPTAS exists which computes a $(1 - \epsilon)$-approximation for Maximum Independent Set on a graph G. I want to use this assumed algorithm as a subroutine in a new algorithm to solve the maximum independent set problem exactly. Now proving that this new algorithm runs in polynomial time would be a contradiction (assuming $P \neq NP)$ since this would mean that I solved the maximum independent set problem in polynomial time. Therefore there exists no FPTAS.

I can't figure out a polynomial time algorithm which uses the above assumed subroutine. How does this algorithm look like, how to use the assumed subroutine (for example what $\epsilon$ to choose?).

$\endgroup$
  • 1
    $\begingroup$ Hint: If $\varepsilon$ is sufficiently small compared to the optimum, a $(1-\varepsilon)$-approximation will necessarily give you the optimum (as solutions to the Independent Set problem are always integers). $\endgroup$ – user53923 Sep 15 '17 at 17:55
  • 1
    $\begingroup$ @user53923 Let $opt$ denote the size of the maximal independent set. My goal is to set $\epsilon$ such that I get a "1-approximation" which would be an exact solution which would give me the contradiction I'm looking for. I would then choose $\epsilon = 1/opt$ which would yield $1-\epsilon = 1-(1/opt) = (opt-1)/opt = opt$ where the last equality comes from the fact that opt is an integer. Does this make sense? I'm not sure about my answer, the last step where I use the fact that opt is an integer bothers me, what if $opt=1$ for example? $\endgroup$ – Anna Vopureta Sep 15 '17 at 22:40
  • 1
    $\begingroup$ You want that $(1-\varepsilon)opt > opt-1$. Your idea for $\varepsilon$ is almost there. Also note that you do not know $opt$, so instead, use an appopriate bound on $opt$. $\endgroup$ – user53923 Sep 16 '17 at 22:13

Your Answer

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

Browse other questions tagged or ask your own question.