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?
Is it possible to approximate Maximum Independent Set in $O(2^k\text{poly}(n))$ time?
ds.algorithms;approximation algorithms;fixed parameter tractable;exp time algorithms