3
$\begingroup$

We know that MIS is hard to approximate within a $n^{1-\epsilon}$ factor in polynomial time and that it is $W[1]$-hard and thus unlikely to admit a $f(k)\text{poly}(n)$ time exact algorithm. (here, $k$ is the size of the independent set).

What about approximating it in FPT time?

Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?

What about other $f(k)$s?

$\endgroup$
1
  • $\begingroup$ I believe this is the state of the art: arxiv.org/abs/1708.03515, and Section 1 gives a good overview of other known results. $\endgroup$ Aug 19, 2017 at 3:36

1 Answer 1

1
$\begingroup$

In the paper: Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses, the authors prove the following bound for Maximum Independent Set:

For any $r$ larger than some constant, any $r$-approximation algorithm for the maximum independent set problem must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ time. This nearly matches the upper bound of $2^{n/r}$.

$\endgroup$
1
  • 3
    $\begingroup$ Assuming ETH**. $\endgroup$
    – R B
    Jul 9, 2017 at 20:01

Your Answer

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

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