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

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?

• 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. – Alex Golovnev Aug 19 '17 at 3:36

1 Answer

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}$.

• Assuming ETH**. – R B Jul 9 '17 at 20:01